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
AC × 3
AC × 11
WA × 2
AC × 19
WA × 9
AC × 23
WA × 20
AC × 27
WA × 35
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