Submission #1013706


Source Code Expand

#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string s;
char s_[111111];
int k;

struct SA {
  string s;
  vector<int> sa, pos;
  int gap;
  
  void build(const string& s_) {
    s = s_;
    sa.resize(s.size());
    pos.resize(s.size());
    auto comp = [&](int a, int b) {
      if (pos[a] != pos[b]) return pos[a] < pos[b];
      a += gap;
      b += gap;
      return (a < int(s.size()) &&
              b < int(s.size())) ? pos[a] < pos[b] : a > b;
    };
    for (size_t i = 0; i < s.size(); i++) {
      sa[i] = i;
      pos[i] = s[i];
    }
    vector<int> t(s.size());
    for (gap = 1;; gap *= 2) {
      sort(sa.begin(), sa.end(), comp);
      for (size_t i = 0; i+1 < s.size(); i++) {
        t[i+1] = t[i] + (comp(sa[i], sa[i+1]) ? 1 : 0);
      }
      for (size_t i = 0; i < s.size(); i++) {
        pos[sa[i]] = t[i];
      }
      if (t.back() == int(s.size())-1) break;
    }
  }
};

SA sa;
vector<int> vs;
int l;

bool test(int j) {
  int c = 0;
  string buf = "";
  string t = s.substr(j, l);
  // printf("%s\n", t.c_str());
  for (size_t i = 0; i < s.size(); i++) {
    // printf("%zd: %d %d\n", i, x, c);
    // printf("%zd: %s %d\n", i, buf.c_str(), c);
    if (l == 1) {
      if (s[i] > t[0]) return false;
    }
    if (((buf+s[i] > t && buf.size()+1 == t.size()) || buf.size()+1 > t.size())) {
      buf = s[i];
      ++c;
    } else {
      buf += s[i];
    }
  }
  return c <= k;
}

int main(void) {
  scanf("%d%s", &k, s_); s = s_;
  sa.build(s);
  l = (s.size()+k)/(k+1);
  for (int i = 0; i < int(sa.sa.size()); i++) {
    if (sa.sa[i]+l <= int(s.size())) {
      vs.push_back(sa.sa[i]);
    }
  }

  int lb = -1;
  int rb = vs.size()-1;
  while (rb-lb > 1) {
    int mb = (lb+rb)/2;
    if (test(vs[mb])) {
      rb = mb;
    } else {
      lb = mb;
    }
  }
  printf("%s\n", s.substr(vs[rb], l).c_str());
  return 0;
}

Submission Info

Submission Time
Task B - Problem where Commas Separate Digits
User roxion1377
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2018 Byte
Status AC
Exec Time 2108 ms
Memory 2168 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%s", &k, s_); s = s_;
                        ^

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 2 ms 256 KB
subtask_01_02.txt AC 2 ms 256 KB
subtask_01_03.txt AC 2 ms 256 KB
subtask_01_04.txt AC 2 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 AC 2 ms 256 KB
subtask_01_09.txt AC 2 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 AC 2 ms 256 KB
subtask_01_14.txt AC 2 ms 256 KB
subtask_01_15.txt AC 2 ms 256 KB
subtask_01_16.txt AC 2 ms 256 KB
subtask_01_17.txt AC 2 ms 256 KB
subtask_02_01.txt AC 2 ms 256 KB
subtask_02_02.txt AC 2 ms 256 KB
subtask_02_03.txt AC 2 ms 256 KB
subtask_02_04.txt AC 2 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 2 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 AC 2 ms 256 KB
subtask_02_14.txt AC 2 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 3 ms 256 KB
subtask_03_03.txt AC 2 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 2 ms 256 KB
subtask_03_07.txt AC 2 ms 256 KB
subtask_03_08.txt AC 3 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 3 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 3 ms 256 KB
subtask_04_01.txt AC 4 ms 256 KB
subtask_04_02.txt AC 5 ms 256 KB
subtask_04_03.txt AC 4 ms 256 KB
subtask_04_04.txt AC 4 ms 256 KB
subtask_04_05.txt AC 4 ms 256 KB
subtask_04_06.txt AC 5 ms 256 KB
subtask_04_07.txt AC 5 ms 256 KB
subtask_04_08.txt AC 5 ms 256 KB
subtask_04_09.txt AC 3 ms 256 KB
subtask_04_10.txt AC 5 ms 256 KB
subtask_04_11.txt AC 5 ms 256 KB
subtask_04_12.txt AC 5 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 155 ms 2168 KB
subtask_05_02.txt AC 157 ms 2168 KB
subtask_05_03.txt AC 95 ms 2168 KB
subtask_05_04.txt AC 144 ms 2168 KB
subtask_05_05.txt AC 155 ms 2168 KB
subtask_05_06.txt AC 156 ms 2168 KB
subtask_05_07.txt AC 165 ms 2168 KB
subtask_05_08.txt AC 2108 ms 1784 KB
subtask_05_09.txt AC 31 ms 1664 KB
subtask_05_10.txt AC 163 ms 2168 KB
subtask_05_11.txt AC 196 ms 2168 KB
subtask_05_12.txt AC 196 ms 2168 KB
subtask_05_13.txt AC 121 ms 1752 KB
subtask_05_14.txt AC 157 ms 2068 KB
subtask_05_15.txt AC 62 ms 1116 KB