Submission #1174419


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;

#define INF (1<<29)
#define INFL (1ll<<60)
#define EPS (1e-8)
#define PI (acos(-1))
const ll MOD = 1000000007ll;

namespace SA
{
	string s;
	vector<int> rank, ord;
	int w;
	
	bool comp(int i, int j) {
		if (rank[i] != rank[j]) return rank[i] < rank[j];
		
		int l = i + w <= s.size() ? rank[i + w] : -1;
		int r = j + w <= s.size() ? rank[j + w] : -1;

		return l < r;
	}
	
	void init(string _s) {
		s = _s;
		
		rank.clear(); rank.resize(s.size() + 1);
		ord.clear(); ord.resize(s.size() + 1);
		
		REP(i, s.size() + 1) {
			rank[i] = i < s.size() ? s[i] : -1;
			ord[i] = i;
		}
		
		for (w = 1; w <= s.size(); w *= 2) {
			sort(ALL(ord), comp);
			
			vector<int> tmp(s.size() + 1);
			tmp[ ord[0] ] = 0;
			FOR(i, 1, s.size() + 1) tmp[ ord[i] ] = tmp[ ord[i - 1] ] + comp(ord[i - 1], ord[i]);
			
			copy(ALL(tmp), rank.begin());
		}
	}
	
	int query(string str) {
		int l = 0, r = s.size();
		while (r - l > 1) {
			int m = (l + r) / 2;
			
			if (s.compare(ord[m], str.size(), str) < 0) l = m;
			else r = m;
		}
		
		if (s.compare(ord[r], str.size(), str) != 0) return -1;
		return ord[r];
	}
}

int main() {
	string S;
	int K;
	cin >> S >> K;
	
	int c = count(ALL(S), 'a');
	
	if (S.size() - c <= K) {
		string ans = "";
		REP(i, S.size() - K) ans += "a";
		cout << ans << endl;
	}
	else {
		SA::init(S);
		
		int l = -1, r = S.size();
		
		while (r - l > 1) {
			int m = (l + r) / 2;
			
			int pos = SA::ord[m];
			int cnt = K;
			bool ok = true;
			
			REP(i, pos) if (S[i] != 'a') {
				if (cnt == 0) {
					ok = false;
					break;
				}
				cnt--;
			}
			
			if (ok) l = m;
			else r = m;
		}
		
		int pos = SA::ord[l];
		int cnt = K;
		
		REP(i, pos) if (S[i] != 'a') {
			S[i] = 'a';
			cnt--;
		}
		
		string tmp = "";
		REP(i, cnt) tmp += "a";
		cout << tmp + S << endl;
	}
	
	return 0;
}

Submission Info

Submission Time
Task C - アメージングな文字列は、きみが作る!
User tkmst201
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2396 Byte
Status WA
Exec Time 467 ms
Memory 5320 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 All
Score / Max Score 0 / 0 0 / 10 0 / 10 0 / 20 0 / 60
Status
AC × 3
AC × 5
WA × 8
AC × 9
WA × 19
AC × 11
WA × 32
AC × 13
WA × 49
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_hand_01.txt, 20_hand_02.txt, 20_hand_03.txt, 20_hand_04.txt, 20_hand_05.txt
Subtask2 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_hand_01.txt, 20_hand_02.txt, 20_hand_03.txt, 20_hand_04.txt, 20_hand_05.txt, 40_rand_01.txt, 40_rand_02.txt, 40_rand_03.txt, 40_rand_04.txt, 40_rand_05.txt, 40_rand_06.txt, 40_rand_07.txt, 40_rand_08.txt, 40_rand_09.txt, 40_rand_10.txt, 50_hand_01.txt, 50_hand_02.txt, 50_hand_03.txt, 50_hand_04.txt, 50_hand_05.txt
Subtask3 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_hand_01.txt, 20_hand_02.txt, 20_hand_03.txt, 20_hand_04.txt, 20_hand_05.txt, 40_rand_01.txt, 40_rand_02.txt, 40_rand_03.txt, 40_rand_04.txt, 40_rand_05.txt, 40_rand_06.txt, 40_rand_07.txt, 40_rand_08.txt, 40_rand_09.txt, 40_rand_10.txt, 50_hand_01.txt, 50_hand_02.txt, 50_hand_03.txt, 50_hand_04.txt, 50_hand_05.txt, 60_rand_01.txt, 60_rand_02.txt, 60_rand_03.txt, 60_rand_04.txt, 60_rand_05.txt, 60_rand_06.txt, 60_rand_07.txt, 60_rand_08.txt, 70_hand_01.txt, 70_hand_02.txt, 70_hand_03.txt, 70_hand_04.txt, 70_hand_05.txt, 70_hand_06.txt, 70_hand_07.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_hand_01.txt, 20_hand_02.txt, 20_hand_03.txt, 20_hand_04.txt, 20_hand_05.txt, 40_rand_01.txt, 40_rand_02.txt, 40_rand_03.txt, 40_rand_04.txt, 40_rand_05.txt, 40_rand_06.txt, 40_rand_07.txt, 40_rand_08.txt, 40_rand_09.txt, 40_rand_10.txt, 50_hand_01.txt, 50_hand_02.txt, 50_hand_03.txt, 50_hand_04.txt, 50_hand_05.txt, 60_rand_01.txt, 60_rand_02.txt, 60_rand_03.txt, 60_rand_04.txt, 60_rand_05.txt, 60_rand_06.txt, 60_rand_07.txt, 60_rand_08.txt, 70_hand_01.txt, 70_hand_02.txt, 70_hand_03.txt, 70_hand_04.txt, 70_hand_05.txt, 70_hand_06.txt, 70_hand_07.txt, 80_rand_01.txt, 80_rand_02.txt, 80_rand_03.txt, 80_rand_04.txt, 80_rand_05.txt, 80_rand_06.txt, 80_rand_07.txt, 80_rand_08.txt, 80_rand_09.txt, 80_rand_10.txt, 90_hand_01.txt, 90_hand_02.txt, 90_hand_03.txt, 90_hand_04.txt, 90_hand_05.txt, 90_hand_06.txt, 90_hand_07.txt, 90_hand_08.txt, 90_hand_09.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
10_rand_01.txt WA 1 ms 256 KB
10_rand_02.txt WA 1 ms 256 KB
10_rand_03.txt WA 1 ms 256 KB
10_rand_04.txt WA 1 ms 256 KB
10_rand_05.txt WA 1 ms 256 KB
20_hand_01.txt AC 1 ms 256 KB
20_hand_02.txt AC 1 ms 256 KB
20_hand_03.txt WA 1 ms 256 KB
20_hand_04.txt WA 1 ms 256 KB
20_hand_05.txt WA 1 ms 256 KB
40_rand_01.txt WA 1 ms 256 KB
40_rand_02.txt WA 1 ms 256 KB
40_rand_03.txt WA 1 ms 256 KB
40_rand_04.txt WA 1 ms 256 KB
40_rand_05.txt WA 1 ms 256 KB
40_rand_06.txt WA 1 ms 256 KB
40_rand_07.txt WA 1 ms 256 KB
40_rand_08.txt WA 1 ms 256 KB
40_rand_09.txt AC 1 ms 256 KB
40_rand_10.txt WA 1 ms 256 KB
50_hand_01.txt AC 1 ms 256 KB
50_hand_02.txt AC 1 ms 256 KB
50_hand_03.txt WA 1 ms 256 KB
50_hand_04.txt WA 1 ms 256 KB
50_hand_05.txt AC 1 ms 256 KB
60_rand_01.txt WA 1 ms 256 KB
60_rand_02.txt WA 1 ms 256 KB
60_rand_03.txt WA 1 ms 256 KB
60_rand_04.txt WA 1 ms 256 KB
60_rand_05.txt WA 1 ms 256 KB
60_rand_06.txt WA 1 ms 256 KB
60_rand_07.txt WA 1 ms 256 KB
60_rand_08.txt WA 1 ms 256 KB
70_hand_01.txt AC 1 ms 256 KB
70_hand_02.txt AC 1 ms 256 KB
70_hand_03.txt WA 2 ms 256 KB
70_hand_04.txt WA 2 ms 256 KB
70_hand_05.txt WA 2 ms 256 KB
70_hand_06.txt WA 2 ms 256 KB
70_hand_07.txt WA 2 ms 256 KB
80_rand_01.txt WA 215 ms 2584 KB
80_rand_02.txt WA 165 ms 2192 KB
80_rand_03.txt WA 370 ms 4100 KB
80_rand_04.txt WA 230 ms 2692 KB
80_rand_05.txt WA 295 ms 3332 KB
80_rand_06.txt WA 295 ms 3356 KB
80_rand_07.txt WA 331 ms 3716 KB
80_rand_08.txt WA 288 ms 3332 KB
80_rand_09.txt WA 331 ms 3760 KB
80_rand_10.txt WA 162 ms 2196 KB
90_hand_01.txt AC 13 ms 1284 KB
90_hand_02.txt AC 11 ms 900 KB
90_hand_03.txt WA 419 ms 5320 KB
90_hand_04.txt WA 420 ms 5320 KB
90_hand_05.txt WA 467 ms 4740 KB
90_hand_06.txt WA 420 ms 4808 KB
90_hand_07.txt WA 423 ms 4808 KB
90_hand_08.txt WA 422 ms 4808 KB
90_hand_09.txt WA 420 ms 4808 KB