Submission #1796951


Source Code Expand

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

class SuffixArray {
	const int n;
	string S;
public:
	vector<int> sa, rank;
	SuffixArray(const string &S_)
		: n(S_.size()), S(S_), sa(n + 1), rank(n + 1)
	{
		for (int i = 0; i <= n; i++) {
			sa[i] = i;
			rank[i] = i < n ? S[i] : -1;
		}
		vector<int> tmp(n + 1);
		for (int k = 1; k <= n; k *= 2) {
			auto Compare_SA = [=](int i, int j) {
				if (rank[i] != rank[j]) return rank[i] < rank[j];

				int ri = i + k <= n ? rank[i + k] : -1;
				int rj = j + k <= n ? rank[j + k] : -1;
				return ri < rj;
			};
			sort(sa.begin(), sa.end(), Compare_SA);

			tmp[sa[0]] = 0;
			for (int i = 1; i <= n; i++) {
				tmp[sa[i]] = tmp[sa[i - 1]] + (Compare_SA(sa[i - 1], sa[i]) ? 1 : 0);
			}
			for (int i = 0; i <= n; i++) {
				rank[i] = tmp[i];
			}
		}
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	string S;
	int K;
	cin >> S >> K;
	int N = S.size();
	vector<int> cnt(N + 1);
	int en = N;
	for (int i = 0; i < N; i++) {
		cnt[i + 1] = cnt[i] + (S[i] == 'a');
		if (i + 1 - cnt[i + 1] > K  && en == N) en = i;
	}
	if (cnt.back() + K >= N) {
		cout << string(N - K, 'a') << endl;
		return 0;
	}
	SuffixArray sa(S);
	int pos = 0;
	for (int i = 0; i < N; i++) {
		if (sa.sa[i] <= en && cnt[pos] < cnt[sa.sa[i]]) {
			pos = sa.sa[i];
		}
	}
	cout << string(K + cnt[pos], 'a') << S.substr(pos, N - pos) << endl;
	return 0;
}

Submission Info

Submission Time
Task C - アメージングな文字列は、きみが作る!
User kazuma
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1449 Byte
Status WA
Exec Time 316 ms
Memory 5652 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 × 7
WA × 6
AC × 17
WA × 11
AC × 29
WA × 14
AC × 45
WA × 17
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 AC 1 ms 256 KB
20_hand_04.txt WA 1 ms 256 KB
20_hand_05.txt AC 1 ms 256 KB
40_rand_01.txt AC 1 ms 256 KB
40_rand_02.txt AC 1 ms 256 KB
40_rand_03.txt WA 1 ms 256 KB
40_rand_04.txt AC 1 ms 256 KB
40_rand_05.txt AC 1 ms 256 KB
40_rand_06.txt WA 1 ms 256 KB
40_rand_07.txt AC 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 AC 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 AC 1 ms 256 KB
60_rand_02.txt AC 1 ms 256 KB
60_rand_03.txt AC 1 ms 256 KB
60_rand_04.txt AC 1 ms 256 KB
60_rand_05.txt AC 1 ms 256 KB
60_rand_06.txt AC 1 ms 256 KB
60_rand_07.txt AC 1 ms 256 KB
60_rand_08.txt AC 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 AC 1 ms 256 KB
70_hand_04.txt WA 1 ms 256 KB
70_hand_05.txt AC 1 ms 256 KB
70_hand_06.txt WA 1 ms 256 KB
70_hand_07.txt WA 1 ms 256 KB
80_rand_01.txt AC 137 ms 3024 KB
80_rand_02.txt AC 102 ms 2512 KB
80_rand_03.txt AC 240 ms 4756 KB
80_rand_04.txt AC 148 ms 3152 KB
80_rand_05.txt AC 192 ms 3988 KB
80_rand_06.txt AC 192 ms 3988 KB
80_rand_07.txt AC 217 ms 4372 KB
80_rand_08.txt AC 187 ms 3860 KB
80_rand_09.txt AC 216 ms 4372 KB
80_rand_10.txt AC 101 ms 2512 KB
90_hand_01.txt AC 3 ms 2324 KB
90_hand_02.txt AC 3 ms 1940 KB
90_hand_03.txt AC 296 ms 5652 KB
90_hand_04.txt WA 297 ms 5652 KB
90_hand_05.txt AC 316 ms 5652 KB
90_hand_06.txt WA 297 ms 5652 KB
90_hand_07.txt WA 301 ms 5652 KB
90_hand_08.txt AC 296 ms 5652 KB
90_hand_09.txt AC 293 ms 5652 KB