Submission #2382072
Source Code Expand
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> // upper_bound(A, A+N, num):>, lower_bound(A, A+N, num):>= #include <functional> #include <string> #include <sstream> #include <complex> #include <vector> // V[i], push_back(x), pop_back(), insert(index, x), erase(index), sort(v.begin(), v.end(), greater<int>()) #include <list> // push_front(x), push_back(x), pop_front(), pop_back(), insert(index, x) #include <queue> // push(x), front(), pop() #include <deque> #include <stack> // push(x), top(), pop() #include <map> // M[key], insert(key, val), erase(key), find(key), #include <set> // insert(key), erase(key), find(key) using namespace std; typedef long long ll; // typedef pair<int, int> P; #define pi 3.141592653589793) #define mod 1000000007 char S[101], T[101]; void solve() { int N, K; cin >> N >> K; cin >> S; vector<int> Tcnt(26); for (int i = 0; i < N; i++) Tcnt[S[i] - 'a']++; for (int i = 0; i < N; i++) { for (char a = 'a'; a < 'z'; a++) { if (Tcnt[a - 'a'] > 0) { T[i] = a; Tcnt[a - 'a']--; int x = 0; for (int j = 0; j < i + 1; j++)x += S[j] != T[j]; vector<int> Scnt(26); for (int j = i + 1; j < N; j++) { Scnt[S[j] - 'a'] ++; } int y = 0; for (int j = 0; j < 26; j++) y += max(Scnt[j], Tcnt[j]) - min(Scnt[j], Tcnt[j]); x += y / 2; if (x <= K) break; Tcnt[a - 'a']++; T[i] = '?'; } } } cout << T << endl; } //const int MAX_N = 100; // //int N, K; //char S[MAX_N]; //string S, T; //map<char,int> mp, mp2; //int change; // //void solve() { // cin >> N >> K >> S; // for (int i = 0; i < N; i++) mp[S[i]]++, mp2[S[i]]++; // // for (int i = 0; i < N; i++) { // // for c in まだ使える文字を小さい順に // for (map<char, int>::iterator itr = mp.begin(); itr != mp.end(); ++itr) { // pair<char, int> p = *itr; // if (mp[p.first]) { // //if T+cにしても大丈夫なら // int dif = 0; // for (int i = 0; i < 26; i++) { // dif += min(mp['a' + i], mp2['a' + i]); // } // // if (K >= dif + change) { // T = T + p.first; // p.second--; // pair<char, int> p2 = *mp2.begin(); // p2.second--; // change++; // break; // } // } // } // } //} int main() { solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 辞書式順序ふたたび |
User | ktguy |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2379 Byte |
Status | WA |
Exec Time | 2 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 | 1 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 | 1 ms | 256 KB |
hand_2_1.txt | AC | 1 ms | 256 KB |
hand_2_10.txt | AC | 1 ms | 256 KB |
hand_2_2.txt | AC | 1 ms | 256 KB |
hand_2_3.txt | AC | 1 ms | 256 KB |
hand_2_4.txt | AC | 1 ms | 256 KB |
hand_2_5.txt | AC | 1 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 | 1 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 | AC | 1 ms | 256 KB |
hand_4_3.txt | AC | 1 ms | 256 KB |
hand_4_4.txt | AC | 1 ms | 256 KB |
hand_4_5.txt | AC | 1 ms | 256 KB |
hand_4_6.txt | AC | 1 ms | 256 KB |
random_1.txt | AC | 1 ms | 256 KB |
random_10.txt | WA | 1 ms | 256 KB |
random_11.txt | WA | 1 ms | 256 KB |
random_12.txt | WA | 1 ms | 256 KB |
random_13.txt | WA | 1 ms | 256 KB |
random_14.txt | WA | 1 ms | 256 KB |
random_15.txt | WA | 1 ms | 256 KB |
random_2.txt | WA | 1 ms | 256 KB |
random_3.txt | WA | 1 ms | 256 KB |
random_4.txt | WA | 1 ms | 256 KB |
random_5.txt | WA | 1 ms | 256 KB |
random_6.txt | WA | 1 ms | 256 KB |
random_7.txt | WA | 2 ms | 256 KB |
random_8.txt | WA | 1 ms | 256 KB |
random_9.txt | WA | 2 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 | WA | 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 |