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
AC × 43
WA × 15
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