Submission #1022032


Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

struct SuffixArray {
  int N, k;
  string S;
  vector<int> sa, rank, tmp;
  vector<int> lpc, rank_lpc;
  SuffixArray(string S) : S(S) {
    N = S.size();
    sa.resize(N+1), rank.resize(N+1), tmp.resize(N+1);
    construct_sa();
  }

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

  void construct_sa() {
    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(), [&] (const int & i, const int & j) { return compare_sa(i, j); });

      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];
    }
  }

  bool contain(string T) {
    int left = 0, right = N;
    while (left - right > 1) {
      int mid = (left + right) / 2;
      (S.compare(sa[mid], T.length(), T) < 0 ? left : right) = mid;
    }
    return S.compare(sa[right], T.length(), T) == 0;
  }

  void construct_lpc() {
    lpc.resize(N), rank_lpc.resize(N+1);
    for (int i = 0; i <= N; i++) rank_lpc[sa[i]] = i;

    int h = 0;
    lpc[0] = 0;
    for (int i = 0; i < N; i++) {
      int j = sa[rank[i] - 1];

      if (h > 0) h--;
      for (; j + h < N and i + h < N; h++) {
        if (S[j + h] != S[i + h]) break;
      }

      lpc[rank[i] - 1] = h;
    }
  }
};

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int K; cin >> K;
  string S; cin >> S;
  int N = S.size();
  SuffixArray sa(S);

  /*
  cout << N << endl;

  REP(i, sa.sa.size()) {
    cout << sa.sa[i] << ' ' << S.substr(sa.sa[i]) << endl;
  }
  */

  vector<int> cand;
  int L = ((int)S.size() + K) / (K + 1);
  //cout << L << endl;
  REP(i, sa.sa.size()) {
    if (sa.sa[i] + L <= N) cand.push_back(sa.sa[i]);
  }

  /*
  cout << endl;
  for (int i : cand) cout << S.substr(i) << endl;
  cout << endl;
  */

  function<bool (int)> check = [&](int mid) {
    int cnt = 0;
    REP(i, N) {
      if (sa.rank[i] <= sa.rank[cand[mid]]) {
        i += L - 1;
        //cout << 0 << ' ' << i << endl;
      } else {
        i += L - 2;
        //cout << 1 << ' ' << i << endl;
      }
      cnt++;
    }
    //cout << cnt << ' ' << mid << ' ' << K << endl;
    return cnt - 1 <= K;
  };

  int left = -1, right = cand.size() - 1;
  while (left + 1 < right) {
    int mid = (left + right) / 2;
    (check(mid) ? right : left) = mid;
  }

  cout << S.substr(cand[right], L) << endl;

  return 0;
}

Submission Info

Submission Time
Task B - Problem where Commas Separate Digits
User n_knuu
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3250 Byte
Status TLE
Exec Time 3154 ms
Memory 2252 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3 Dataset4 Dataset5
Score / Max Score 0 / 0 0 / 100 0 / 100 0 / 200 0 / 200 0 / 400
Status
AC × 3
AC × 12
TLE × 5
AC × 25
TLE × 7
AC × 41
TLE × 8
AC × 55
TLE × 9
AC × 69
TLE × 10
Set Name Test Cases
Sample subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt
Dataset1 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt
Dataset2 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt
Dataset3 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt
Dataset4 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt
Dataset5 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 3 ms 256 KB
subtask_01_02.txt TLE 3154 ms 256 KB
subtask_01_03.txt TLE 3154 ms 256 KB
subtask_01_04.txt AC 3 ms 256 KB
subtask_01_05.txt AC 2 ms 256 KB
subtask_01_06.txt AC 2 ms 256 KB
subtask_01_07.txt AC 2 ms 256 KB
subtask_01_08.txt TLE 3154 ms 256 KB
subtask_01_09.txt AC 3 ms 256 KB
subtask_01_10.txt AC 2 ms 256 KB
subtask_01_11.txt AC 2 ms 256 KB
subtask_01_12.txt AC 2 ms 256 KB
subtask_01_13.txt TLE 3154 ms 256 KB
subtask_01_14.txt AC 2 ms 256 KB
subtask_01_15.txt TLE 3154 ms 256 KB
subtask_01_16.txt AC 3 ms 256 KB
subtask_01_17.txt AC 2 ms 256 KB
subtask_02_01.txt AC 3 ms 256 KB
subtask_02_02.txt AC 2 ms 256 KB
subtask_02_03.txt TLE 3154 ms 256 KB
subtask_02_04.txt AC 3 ms 256 KB
subtask_02_05.txt AC 2 ms 256 KB
subtask_02_06.txt AC 2 ms 256 KB
subtask_02_07.txt AC 2 ms 256 KB
subtask_02_08.txt AC 2 ms 256 KB
subtask_02_09.txt AC 2 ms 256 KB
subtask_02_10.txt AC 3 ms 256 KB
subtask_02_11.txt AC 2 ms 256 KB
subtask_02_12.txt AC 2 ms 256 KB
subtask_02_13.txt TLE 3154 ms 256 KB
subtask_02_14.txt AC 3 ms 256 KB
subtask_02_ex1.txt AC 2 ms 256 KB
subtask_03_01.txt AC 2 ms 256 KB
subtask_03_02.txt AC 2 ms 256 KB
subtask_03_03.txt TLE 3154 ms 256 KB
subtask_03_04.txt AC 3 ms 256 KB
subtask_03_05.txt AC 2 ms 256 KB
subtask_03_06.txt AC 2 ms 256 KB
subtask_03_07.txt AC 2 ms 256 KB
subtask_03_08.txt AC 2 ms 256 KB
subtask_03_09.txt AC 2 ms 256 KB
subtask_03_10.txt AC 2 ms 256 KB
subtask_03_11.txt AC 3 ms 256 KB
subtask_03_12.txt AC 2 ms 256 KB
subtask_03_13.txt AC 2 ms 256 KB
subtask_03_14.txt AC 2 ms 256 KB
subtask_03_15.txt AC 2 ms 256 KB
subtask_03_ex2.txt AC 2 ms 256 KB
subtask_03_ex3.txt AC 2 ms 256 KB
subtask_04_01.txt AC 3 ms 256 KB
subtask_04_02.txt AC 3 ms 256 KB
subtask_04_03.txt TLE 3154 ms 256 KB
subtask_04_04.txt AC 3 ms 256 KB
subtask_04_05.txt AC 3 ms 256 KB
subtask_04_06.txt AC 3 ms 256 KB
subtask_04_07.txt AC 3 ms 256 KB
subtask_04_08.txt AC 3 ms 256 KB
subtask_04_09.txt AC 3 ms 256 KB
subtask_04_10.txt AC 3 ms 256 KB
subtask_04_11.txt AC 3 ms 256 KB
subtask_04_12.txt AC 3 ms 256 KB
subtask_04_13.txt AC 3 ms 256 KB
subtask_04_14.txt AC 3 ms 256 KB
subtask_04_15.txt AC 3 ms 256 KB
subtask_05_01.txt AC 83 ms 2252 KB
subtask_05_02.txt AC 84 ms 2252 KB
subtask_05_03.txt TLE 3154 ms 2252 KB
subtask_05_04.txt AC 82 ms 2252 KB
subtask_05_05.txt AC 81 ms 2252 KB
subtask_05_06.txt AC 80 ms 2252 KB
subtask_05_07.txt AC 80 ms 2252 KB
subtask_05_08.txt AC 79 ms 2000 KB
subtask_05_09.txt AC 79 ms 1872 KB
subtask_05_10.txt AC 82 ms 2252 KB
subtask_05_11.txt AC 79 ms 2252 KB
subtask_05_12.txt AC 70 ms 2252 KB
subtask_05_13.txt AC 57 ms 1916 KB
subtask_05_14.txt AC 74 ms 2240 KB
subtask_05_15.txt AC 29 ms 1280 KB