CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1291541

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

struct SuffixArray
{
  vector< int > SA;
  string s;

  void Build_SA(const string &str)
  {
    s = str;
    SA.resize(s.size());
    iota(begin(SA), end(SA), 0);
    sort(begin(SA), end(SA), [&](const int &a, const int &b)
    {
      if(s[a] == s[b]) return (a > b);
      return (s[a] < s[b]);
    });
    vector< int > classes(s.size()), c(s.size()), cnt(s.size());
    for(int i = 0; i < s.size(); i++) {
      c[i] = s[i];
    }
    for(int len = 1; len < s.size(); len <<= 1) {
      for(int i = 0; i < s.size(); i++) {
        if(i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) {
          classes[SA[i]] = classes[SA[i - 1]];
        } else {
          classes[SA[i]] = i;
        }
      }
      iota(begin(cnt), end(cnt), 0);
      copy(begin(SA), end(SA), begin(c));
      for(int i = 0; i < s.size(); i++) {
        int s1 = c[i] - len;
        if(s1 >= 0) SA[cnt[classes[s1]]++] = s1;
      }
      classes.swap(c);
    }
  }

  int operator[](int k) const
  {
    return (SA[k]);
  }

  int size() const
  {
    return (s.size());
  }

  bool lt_substr(string &t, int si = 0, int ti = 0)
  {
    int sn = s.size(), tn = t.size();
    while(si < sn && ti < tn) {
      if(s[si] < t[ti]) return (true);
      if(s[si] > t[ti]) return (false);
      ++si, ++ti;
    }
    return (si >= sn && ti < tn);
  }

  int lower_bound(string &t)
  {
    int low = -1, high = SA.size();
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    return (high);
  }

  pair< int, int > lower_upper_bound(string &t)
  {
    int idx = lower_bound(t);
    int low = idx - 1, high = SA.size();
    t.back()++;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    t.back()--;
    return (make_pair(idx, high));
  }

  void output()
  {
    for(int i = 0; i < size(); i++) {
      cout << i << ": " << s.substr(SA[i]) << endl;
    }
  }
};


int main()
{
  int K;
  string S;

  cin >> K;
  cin >> S;

  SuffixArray sa;
  sa.Build_SA(S);
  //sa.output();

  int L = (S.size() + K) / (K + 1);
  vector< int > rev(S.size());
  for(int i = 0; i < S.size(); i++) rev[sa[i]] = i;

  auto check = [&](int v)
  {
    int ret = 0;
    for(int i = 0; i < S.size(); ++ret) {
      int add = rev[i] < v ? L : L - 1;
      if(add == 0) return (false);
      i += add;
    }
    return (ret <= K + 1);
  };

  int low = 0, high = sa.size();
  while(high - low > 1) {
    int mid = (low + high) >> 1;
    if(check(mid)) high = mid;
    else low = mid;
  }
  cout << S.substr(sa[low], L) << endl;
}

Submission

Task問題 B - 数字列をカンマで分ける問題 / Problem where Commas Separate Digits
User nameユーザ名 タプリスちゃん
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1000
Source lengthソースコード長 2887 Byte
File nameファイル名
Exec time実行時間 49 ms
Memory usageメモリ使用量 2048 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask_02_ex1.txt,subtask_03_ex2.txt,subtask_03_ex3.txt
Dataset1 100 / 100 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 100 / 100 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 200 / 200 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 200 / 200 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 400 / 400 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 1 ms 256 KB
subtask_01_02.txt AC 1 ms 256 KB
subtask_01_03.txt AC 1 ms 256 KB
subtask_01_04.txt AC 1 ms 256 KB
subtask_01_05.txt AC 1 ms 256 KB
subtask_01_06.txt AC 1 ms 256 KB
subtask_01_07.txt AC 1 ms 256 KB
subtask_01_08.txt AC 1 ms 256 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 1 ms 256 KB
subtask_01_11.txt AC 1 ms 256 KB
subtask_01_12.txt AC 1 ms 256 KB
subtask_01_13.txt AC 1 ms 256 KB
subtask_01_14.txt AC 1 ms 256 KB
subtask_01_15.txt AC 1 ms 256 KB
subtask_01_16.txt AC 1 ms 256 KB
subtask_01_17.txt AC 1 ms 256 KB
subtask_02_01.txt AC 1 ms 256 KB
subtask_02_02.txt AC 1 ms 256 KB
subtask_02_03.txt AC 1 ms 256 KB
subtask_02_04.txt AC 1 ms 256 KB
subtask_02_05.txt AC 1 ms 256 KB
subtask_02_06.txt AC 1 ms 256 KB
subtask_02_07.txt AC 1 ms 256 KB
subtask_02_08.txt AC 1 ms 256 KB
subtask_02_09.txt AC 1 ms 256 KB
subtask_02_10.txt AC 1 ms 256 KB
subtask_02_11.txt AC 1 ms 256 KB
subtask_02_12.txt AC 1 ms 256 KB
subtask_02_13.txt AC 1 ms 256 KB
subtask_02_14.txt AC 1 ms 256 KB
subtask_02_ex1.txt AC 1 ms 256 KB
subtask_03_01.txt AC 1 ms 256 KB
subtask_03_02.txt AC 1 ms 256 KB
subtask_03_03.txt AC 1 ms 256 KB
subtask_03_04.txt AC 1 ms 256 KB
subtask_03_05.txt AC 1 ms 256 KB
subtask_03_06.txt AC 1 ms 256 KB
subtask_03_07.txt AC 1 ms 256 KB
subtask_03_08.txt AC 1 ms 256 KB
subtask_03_09.txt AC 1 ms 256 KB
subtask_03_10.txt AC 1 ms 256 KB
subtask_03_11.txt AC 1 ms 256 KB
subtask_03_12.txt AC 1 ms 256 KB
subtask_03_13.txt AC 1 ms 256 KB
subtask_03_14.txt AC 1 ms 256 KB
subtask_03_15.txt AC 1 ms 256 KB
subtask_03_ex2.txt AC 1 ms 256 KB
subtask_03_ex3.txt AC 1 ms 256 KB
subtask_04_01.txt AC 2 ms 256 KB
subtask_04_02.txt AC 2 ms 256 KB
subtask_04_03.txt AC 2 ms 256 KB
subtask_04_04.txt AC 2 ms 256 KB
subtask_04_05.txt AC 2 ms 256 KB
subtask_04_06.txt AC 2 ms 256 KB
subtask_04_07.txt AC 2 ms 256 KB
subtask_04_08.txt AC 2 ms 256 KB
subtask_04_09.txt AC 2 ms 256 KB
subtask_04_10.txt AC 2 ms 256 KB
subtask_04_11.txt AC 2 ms 256 KB
subtask_04_12.txt AC 1 ms 256 KB
subtask_04_13.txt AC 1 ms 256 KB
subtask_04_14.txt AC 1 ms 256 KB
subtask_04_15.txt AC 1 ms 256 KB
subtask_05_01.txt AC 49 ms 2048 KB
subtask_05_02.txt AC 48 ms 2048 KB
subtask_05_03.txt AC 44 ms 2048 KB
subtask_05_04.txt AC 46 ms 2048 KB
subtask_05_05.txt AC 45 ms 2048 KB
subtask_05_06.txt AC 45 ms 2048 KB
subtask_05_07.txt AC 44 ms 2048 KB
subtask_05_08.txt AC 43 ms 2048 KB
subtask_05_09.txt AC 43 ms 2048 KB
subtask_05_10.txt AC 40 ms 2048 KB
subtask_05_11.txt AC 27 ms 2048 KB
subtask_05_12.txt AC 20 ms 2048 KB
subtask_05_13.txt AC 32 ms 1664 KB
subtask_05_14.txt AC 40 ms 1920 KB
subtask_05_15.txt AC 16 ms 1024 KB