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 |
|
|
|
|
|
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 |