Submission #1780669
Source Code Expand
#include <iostream> #include <iomanip> #include <vector> #include <valarray> #include <map> #include <set> #include <list> #include <queue> #include <stack> #include <bitset> #include <utility> #include <numeric> #include <algorithm> #include <functional> #include <complex> #include <string> #include <sstream> #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> #include <cmath> using namespace std; #define all(c) c.begin(),c.end() #define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++) #define debug(x) #x << "=" << (x) #define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl typedef long long ll; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<string> vs; template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec){ os << "["; for(int i = 0; i < vec.size(); i++){ os << vec[i] << ","; } os << "]"; return os; } template<typename T> T input(){ T t; cin >> t; return t; } template<typename T> vector<T> input(const int N){ vector<T> v(N); repeat(i,N) cin >> v[i]; return v; } long long gcd(long long a, long long b){ if(b == 0){ return a; } return gcd(b, a % b); } long long lcm(long long a, long long b){ return (a / gcd(a, b)) * b; } long long mul(const long long& a, const long long& b, const long long& mod) { return ((a % mod) * (b % mod)) % mod; } long long power(const long long& x, const long long& y, const long long& mod) { if (y == 0) { return 1; } else if (y == 1) { return x % mod; } else { long long value = power(x, y / 2, mod); if (y % 2 == 0) { return mul(value, value, mod); } else { return mul(value, value, mod) * x % mod; } } } long long div(const long long& a, const long long& b, const long long& mod) { return mul(a, power(b, mod - 2, mod), mod); } map<long long, long long> factorials; long long factorial(const long long& n, const long long& mod) { if (n == 0 || n == 1) { return 1; } if (factorials[n] != 0) { return factorials[n]; } factorials[n] = n * factorial(n - 1, mod) % mod; return factorials[n] % mod; } long long combination(const long long& n, const long long& x, const long long& mod) { long long numerator = 1; long long denominator = 1; repeat(i, x) { numerator *= (n - i) % mod; numerator %= mod; denominator *= (i + 1) % mod; denominator %= mod; } return div(numerator, denominator, mod); } string removedString(const string& original, string charactersToRemove) { string removed = ""; repeat (i, original.size()) { int index; if ((index = charactersToRemove.find(original[i])) != string::npos) { charactersToRemove = charactersToRemove.erase(index, 1); } else { removed += original[i]; } } return removed; } bool isReachable(const string& original, const string& candidate, const int& K) { int changed = 0; repeat (i, original.size()) { if (original[i] != candidate[i]) { changed++; } } return changed <= K; } string sortAlphabetically(const string& original, const string& sorted, const int& K) { string candidate = original; for (int i = K; 0 <= i ; --i) { string head = sorted.substr(0, i); string tail = removedString(original, head); sort(tail.begin(), tail.end()); do { candidate = head + tail; if (isReachable(original, candidate, K)) { break; } } while (next_permutation(tail.begin(), tail.end())); } return candidate; } int main(){ int N, K; cin >> N >> K; string original; cin >> original; string sorted = original; sort(sorted.begin(), sorted.end()); cout << sortAlphabetically(original, sorted, K) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 辞書式順序ふたたび |
User | xeonics |
Language | C++11 (GCC 4.8.1) |
Score | 0 |
Code Size | 4000 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 256 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | hand_1_0.txt, hand_1_1.txt, hand_1_2.txt, hand_1_3.txt, hand_1_4.txt, hand_1_5.txt, hand_1_6.txt, hand_1_7.txt, hand_1_8.txt, hand_2_0.txt, hand_2_1.txt, hand_2_10.txt, hand_2_2.txt, hand_2_3.txt, hand_2_4.txt, hand_2_5.txt, hand_2_6.txt, hand_2_7.txt, hand_2_8.txt, hand_2_9.txt, hand_3_2.txt, hand_3_3.txt, hand_3_4.txt, hand_3_5.txt, hand_3_6.txt, hand_4_2.txt, hand_4_3.txt, hand_4_4.txt, hand_4_5.txt, hand_4_6.txt, random_1.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
hand_1_0.txt | AC | 1 ms | 256 KB |
hand_1_1.txt | AC | 2 ms | 256 KB |
hand_1_2.txt | AC | 1 ms | 256 KB |
hand_1_3.txt | AC | 1 ms | 256 KB |
hand_1_4.txt | AC | 1 ms | 256 KB |
hand_1_5.txt | AC | 1 ms | 256 KB |
hand_1_6.txt | AC | 1 ms | 256 KB |
hand_1_7.txt | AC | 1 ms | 256 KB |
hand_1_8.txt | AC | 1 ms | 256 KB |
hand_2_0.txt | AC | 10 ms | 256 KB |
hand_2_1.txt | AC | 13 ms | 256 KB |
hand_2_10.txt | AC | 1 ms | 256 KB |
hand_2_2.txt | AC | 5 ms | 256 KB |
hand_2_3.txt | AC | 5 ms | 256 KB |
hand_2_4.txt | AC | 2 ms | 256 KB |
hand_2_5.txt | AC | 2 ms | 256 KB |
hand_2_6.txt | AC | 1 ms | 256 KB |
hand_2_7.txt | AC | 1 ms | 256 KB |
hand_2_8.txt | AC | 1 ms | 256 KB |
hand_2_9.txt | AC | 1 ms | 256 KB |
hand_3_2.txt | AC | 2 ms | 256 KB |
hand_3_3.txt | AC | 1 ms | 256 KB |
hand_3_4.txt | AC | 1 ms | 256 KB |
hand_3_5.txt | AC | 1 ms | 256 KB |
hand_3_6.txt | AC | 1 ms | 256 KB |
hand_4_2.txt | TLE | 2103 ms | 256 KB |
hand_4_3.txt | TLE | 2103 ms | 256 KB |
hand_4_4.txt | TLE | 2103 ms | 256 KB |
hand_4_5.txt | TLE | 2103 ms | 256 KB |
hand_4_6.txt | TLE | 2103 ms | 256 KB |
random_1.txt | TLE | 2103 ms | 256 KB |
random_10.txt | TLE | 2103 ms | 256 KB |
random_11.txt | TLE | 2103 ms | 256 KB |
random_12.txt | TLE | 2103 ms | 256 KB |
random_13.txt | TLE | 2103 ms | 256 KB |
random_14.txt | TLE | 2103 ms | 256 KB |
random_15.txt | AC | 2 ms | 256 KB |
random_2.txt | TLE | 2103 ms | 256 KB |
random_3.txt | TLE | 2103 ms | 256 KB |
random_4.txt | TLE | 2103 ms | 256 KB |
random_5.txt | AC | 1 ms | 256 KB |
random_6.txt | TLE | 2103 ms | 256 KB |
random_7.txt | TLE | 2103 ms | 256 KB |
random_8.txt | TLE | 2103 ms | 256 KB |
random_9.txt | TLE | 2103 ms | 256 KB |
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 1 ms | 256 KB |
sample_4.txt | AC | 1 ms | 256 KB |
small_1.txt | AC | 1 ms | 256 KB |
small_2.txt | AC | 1 ms | 256 KB |
small_3.txt | AC | 1 ms | 256 KB |
small_4.txt | AC | 1 ms | 256 KB |
small_5.txt | AC | 1 ms | 256 KB |
small_6.txt | AC | 1 ms | 256 KB |
small_7.txt | AC | 1 ms | 256 KB |
small_8.txt | AC | 1 ms | 256 KB |
small_9.txt | AC | 1 ms | 256 KB |