Submission #1834481
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 rank(N + 1); vi tmp(N + 1); // (rank[i], rank[i + k]) と (rank[j], rank[j + k]) を比較 bool compare_sa(int i, int j) { if (rank[i] != rank[j]) return rank[i] < rank[j]; else { int ri = i + k <= n ? rank[i + k] : -1; int rj = j + k <= n ? rank[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; rank[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++) { rank[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 | 2728 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘bool compare_sa(int, int)’: ./Main.cpp:32:7: error: reference to ‘rank’ is ambiguous if (rank[i] != rank[j]) return rank[i] < rank[j]; ^ ./Main.cpp:27:4: note: candidates are: std::vector<int> rank vi rank(N + 1); ^ In file included from /usr/include/c++/5/bits/move.h:57:0, from /usr/include/c++/5/bits/stl_pair.h:59, from /usr/include/c++/5/bits/stl_algobase.h:64, from /usr/include/c++/5/bits/char_traits.h:39, from /usr/include/c++/5/ios:40, from /usr/include/c++/5/istream:38, from /usr/include/c++/5/sstream:38, from /usr/include/c++/5/complex:45, from /usr/include/c++/5/ccomplex:38, from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52, from ./Main.cpp:1: /usr/include/c++/5/type_traits:1415:12: note: template<class> struct std::rank struct rank ^ ./Main.cpp:32:18:...