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