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