Submission #1003162


Source Code Expand

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef vector<int> VI;

/*
 * Suffix Array.
 * Required Headers: algorithm, cassert, string, vector
 * Verified by: http://arc050.contest.atcoder.jp/submissions/818745
 * Reference: http://mayokoex.hatenablog.com/entry/2016/04/03/145845
 */
struct compare_sa {
  const std::vector<int> &rank;
  int n, k;
  compare_sa(const std::vector<int> &rank, int n, int k) : rank(rank), n(n), k(k) {}
  bool operator () (int i, int j) {
    if (rank[i] != rank[j]) {
      return rank[i] < rank[j];
    }
    int ri = i + k <= n ? rank[i + k] : -1;
    int rj = j + k <= n ? rank[j + k] : -1;
    return ri < rj;
  }
};

std::vector<int> create_sa(const std::string& s) {
  int n = s.length();
  std::vector<int> sa(n + 1, -1);
  std::vector<int> rank(n + 1, -1);
  std::vector<int> tmp(n + 1, -1);
  
  for (int i = 0; i <= n; ++i) {
    sa[i] = i;
    rank[i] = i < n ? s[i] : -1;
  }
  
  for (int k = 1; k <= n; k *= 2) {
    compare_sa cp = compare_sa(rank, n, k);
    std::sort(sa.begin(), sa.begin() + n + 1, cp);
    tmp[sa[0]] = 0;
    for (int i = 1; i <= n; ++i) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (cp(sa[i - 1], sa[i]) ? 1 : 0);
    }
    for (int i = 0; i <= n; ++i) {
      rank[i] = tmp[i];
    }
  }
  return sa;
}

int main(void){
  int k;
  string s;
  cin >> k >> s;
  if (k == 0) {
    cout << s << endl;
    return 0;
  }
  int n = s.length();
  VI sa = create_sa(s);
  VI sa_inv(n + 1);
  REP(i, 0, n + 1) {
    sa_inv[sa[i]] = i;
  }
  VI sat;
  int q = (n + k) / (k + 1);
  int r = q * (k + 1) - n; // 0 <= r <= k
  REP(i, 0, sa.size()) {
    int w = sa[i];
    if (w <= n - q) {
      sat.push_back(w);
    }
  }
  int lo = -1;
  int hi = n - q + 1;
  while (hi - lo > 1) {
    int mid = (hi + lo) / 2;
    // try to divide, so that all the divided strings <= s[sat[mid]..]
    // We want to avoid making more than r strings of length q - 1.
    int rem = r;
    REP(i, 0, k + 1) {
      if (rem < 0) {
	break;
      }
      int idx = i * q - r + rem;
      if (idx >= n - q + 1) {
	break;
      }
      if (sa_inv[idx] > sa_inv[sat[mid]]) {
	rem--;
      }
    }
    if (rem >= 0) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  cout << s.substr(sat[hi], q) << endl;
}

Submission Info

Submission Time
Task B - Problem where Commas Separate Digits
User kobae964
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2372 Byte
Status AC
Exec Time 90 ms
Memory 2032 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3 Dataset4 Dataset5
Score / Max Score 0 / 0 100 / 100 100 / 100 200 / 200 200 / 200 400 / 400
Status
AC × 3
AC × 17
AC × 32
AC × 49
AC × 64
AC × 79
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 AC 3 ms 256 KB
subtask_01_03.txt AC 3 ms 256 KB
subtask_01_04.txt AC 3 ms 256 KB
subtask_01_05.txt AC 3 ms 256 KB
subtask_01_06.txt AC 3 ms 256 KB
subtask_01_07.txt AC 3 ms 256 KB
subtask_01_08.txt AC 3 ms 256 KB
subtask_01_09.txt AC 3 ms 256 KB
subtask_01_10.txt AC 3 ms 256 KB
subtask_01_11.txt AC 3 ms 256 KB
subtask_01_12.txt AC 3 ms 256 KB
subtask_01_13.txt AC 3 ms 256 KB
subtask_01_14.txt AC 3 ms 256 KB
subtask_01_15.txt AC 3 ms 256 KB
subtask_01_16.txt AC 3 ms 256 KB
subtask_01_17.txt AC 3 ms 256 KB
subtask_02_01.txt AC 3 ms 256 KB
subtask_02_02.txt AC 3 ms 256 KB
subtask_02_03.txt AC 3 ms 256 KB
subtask_02_04.txt AC 3 ms 256 KB
subtask_02_05.txt AC 3 ms 256 KB
subtask_02_06.txt AC 3 ms 256 KB
subtask_02_07.txt AC 3 ms 256 KB
subtask_02_08.txt AC 3 ms 256 KB
subtask_02_09.txt AC 3 ms 256 KB
subtask_02_10.txt AC 3 ms 256 KB
subtask_02_11.txt AC 3 ms 256 KB
subtask_02_12.txt AC 3 ms 256 KB
subtask_02_13.txt AC 3 ms 256 KB
subtask_02_14.txt AC 3 ms 256 KB
subtask_02_ex1.txt AC 3 ms 256 KB
subtask_03_01.txt AC 3 ms 256 KB
subtask_03_02.txt AC 3 ms 256 KB
subtask_03_03.txt AC 3 ms 256 KB
subtask_03_04.txt AC 3 ms 256 KB
subtask_03_05.txt AC 3 ms 256 KB
subtask_03_06.txt AC 3 ms 256 KB
subtask_03_07.txt AC 3 ms 256 KB
subtask_03_08.txt AC 3 ms 256 KB
subtask_03_09.txt AC 3 ms 256 KB
subtask_03_10.txt AC 3 ms 256 KB
subtask_03_11.txt AC 3 ms 256 KB
subtask_03_12.txt AC 3 ms 256 KB
subtask_03_13.txt AC 3 ms 256 KB
subtask_03_14.txt AC 3 ms 256 KB
subtask_03_15.txt AC 3 ms 256 KB
subtask_03_ex2.txt AC 3 ms 256 KB
subtask_03_ex3.txt AC 3 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 AC 3 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 89 ms 2032 KB
subtask_05_02.txt AC 90 ms 2032 KB
subtask_05_03.txt AC 87 ms 2032 KB
subtask_05_04.txt AC 86 ms 2032 KB
subtask_05_05.txt AC 86 ms 2032 KB
subtask_05_06.txt AC 86 ms 2032 KB
subtask_05_07.txt AC 86 ms 2032 KB
subtask_05_08.txt AC 86 ms 1664 KB
subtask_05_09.txt AC 6 ms 512 KB
subtask_05_10.txt AC 88 ms 2032 KB
subtask_05_11.txt AC 85 ms 2032 KB
subtask_05_12.txt AC 77 ms 2032 KB
subtask_05_13.txt AC 61 ms 1840 KB
subtask_05_14.txt AC 79 ms 1960 KB
subtask_05_15.txt AC 32 ms 1080 KB