Submission #1834487
Source Code Expand
#include "bits/stdc++.h" using namespace std; #define DEBUG(x) cout<<#x<<": "<<x<<endl; #define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl typedef long long ll; #define vi vector<int> #define vl vector<ll> #define vii vector< vector<int> > #define vll vector< vector<ll> > #define vs vector<string> #define pii pair<int,int> #define pis pair<int,string> #define psi pair<string,int> const int inf = 1000000001; const ll INF = 1e16; #define MOD 1000000007 #define mod 1000000009 #define pi 3.14159265358979323846 #define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl; int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 }; #define N 300010 int n, k; vi rank2(N + 1); vi tmp(N + 1); // (rank[i], rank[i + k]) と (rank[j], rank[j + k]) を比較 bool compare_sa(int i, int j) { if (rank2[i] != rank2[j]) return rank2[i] < rank2[j]; else { int ri = i + k <= n ? rank2[i + k] : -1; int rj = j + k <= n ? rank2[j + k] : -1; return ri < rj; } } // 文字列sの接尾辞配列を構築、ダブリングの原理 vi construct_sa(string s) { n = s.size(); vi sa(n + 1); //最初は一文字、ランクは文字コードにすれば良い for (int i = 0; i <= n; i++) { sa[i] = i; rank2[i] = i < n ? s[i] : -1; } for (k = 1; k <= n; k *= 2) { sort(sa.begin(), sa.end(), compare_sa); //一旦tmpに次のランクを計算しそれをrankに移す 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++) { rank2[i] = tmp[i]; } } return sa; } int main() { string s; cin >> s; int m, i, j; cin >> m; int cnt = 0; for (i = 0; i < s.size(); i++) { if (s[i] != 'a') { cnt++; } } if (cnt <= m) { for (i = 0; i < s.size() - cnt; i++) { cout << 'a'; } cout << endl; return 0; } vi sa = construct_sa(s); vi revsa(sa.size()); for (i = 0; i < sa.size(); i++) { revsa[sa[i]] = i; } //DEBUG_VEC(sa); //DEBUG_VEC(revsa); cnt = 0; int mn = inf; int idx = -1; for (i = 0; i < s.size(); i++) { if (s[i] != 'a') { if (mn > revsa[i]) { idx = i; mn = revsa[i]; } cnt++; if (cnt >= m + 1) { break; } } } //cout << idx << endl; cnt = 0; for (i = 0; i < idx; i++) { if (s[i] != 'a') { s[i] = 'a'; cnt++; } } //cout << cnt << endl; for (i = 0; i < m - cnt; i++) { cout << "a"; } cout << s << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - アメージングな文字列は、きみが作る! |
User | fuppy0716 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2737 Byte |
Status | WA |
Exec Time | 482 ms |
Memory | 5980 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 | 3 ms | 2560 KB |
00_example_02.txt | AC | 3 ms | 2560 KB |
00_example_03.txt | AC | 3 ms | 2560 KB |
10_rand_01.txt | AC | 3 ms | 2560 KB |
10_rand_02.txt | AC | 3 ms | 2560 KB |
10_rand_03.txt | AC | 3 ms | 2560 KB |
10_rand_04.txt | AC | 3 ms | 2560 KB |
10_rand_05.txt | AC | 3 ms | 2560 KB |
20_hand_01.txt | WA | 3 ms | 2560 KB |
20_hand_02.txt | AC | 3 ms | 2560 KB |
20_hand_03.txt | AC | 3 ms | 2560 KB |
20_hand_04.txt | AC | 3 ms | 2560 KB |
20_hand_05.txt | WA | 3 ms | 2560 KB |
40_rand_01.txt | WA | 3 ms | 2560 KB |
40_rand_02.txt | WA | 3 ms | 2560 KB |
40_rand_03.txt | AC | 3 ms | 2560 KB |
40_rand_04.txt | AC | 3 ms | 2560 KB |
40_rand_05.txt | WA | 3 ms | 2560 KB |
40_rand_06.txt | AC | 3 ms | 2560 KB |
40_rand_07.txt | WA | 3 ms | 2560 KB |
40_rand_08.txt | AC | 3 ms | 2560 KB |
40_rand_09.txt | AC | 3 ms | 2560 KB |
40_rand_10.txt | AC | 3 ms | 2560 KB |
50_hand_01.txt | WA | 3 ms | 2560 KB |
50_hand_02.txt | WA | 3 ms | 2560 KB |
50_hand_03.txt | AC | 3 ms | 2560 KB |
50_hand_04.txt | AC | 3 ms | 2560 KB |
50_hand_05.txt | WA | 2 ms | 2560 KB |
60_rand_01.txt | WA | 3 ms | 2560 KB |
60_rand_02.txt | WA | 3 ms | 2560 KB |
60_rand_03.txt | WA | 3 ms | 2560 KB |
60_rand_04.txt | WA | 3 ms | 2560 KB |
60_rand_05.txt | WA | 3 ms | 2560 KB |
60_rand_06.txt | WA | 3 ms | 2560 KB |
60_rand_07.txt | WA | 3 ms | 2560 KB |
60_rand_08.txt | WA | 3 ms | 2560 KB |
70_hand_01.txt | WA | 3 ms | 2560 KB |
70_hand_02.txt | WA | 3 ms | 2560 KB |
70_hand_03.txt | AC | 3 ms | 2560 KB |
70_hand_04.txt | AC | 3 ms | 2560 KB |
70_hand_05.txt | WA | 3 ms | 2560 KB |
70_hand_06.txt | AC | 3 ms | 2560 KB |
70_hand_07.txt | AC | 3 ms | 2560 KB |
80_rand_01.txt | WA | 219 ms | 4204 KB |
80_rand_02.txt | WA | 167 ms | 3968 KB |
80_rand_03.txt | WA | 375 ms | 5260 KB |
80_rand_04.txt | WA | 235 ms | 4324 KB |
80_rand_05.txt | WA | 299 ms | 4796 KB |
80_rand_06.txt | WA | 300 ms | 4796 KB |
80_rand_07.txt | WA | 337 ms | 5028 KB |
80_rand_08.txt | WA | 297 ms | 4672 KB |
80_rand_09.txt | WA | 333 ms | 4900 KB |
80_rand_10.txt | WA | 165 ms | 3968 KB |
90_hand_01.txt | WA | 21 ms | 3332 KB |
90_hand_02.txt | WA | 17 ms | 3204 KB |
90_hand_03.txt | AC | 428 ms | 5980 KB |
90_hand_04.txt | AC | 422 ms | 5596 KB |
90_hand_05.txt | WA | 482 ms | 5596 KB |
90_hand_06.txt | AC | 422 ms | 5596 KB |
90_hand_07.txt | AC | 422 ms | 5596 KB |
90_hand_08.txt | WA | 427 ms | 5852 KB |
90_hand_09.txt | WA | 424 ms | 5852 KB |