Submission #1003240


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,k;
char s[125252];

const int B = 10007;
// hash[i] := [0,i)
int hsh[125252];
int bpow[125252];
// subhash(l,r) := [l,r) = [0,r) - [0,l) * bpow[r-l]
inline int subhash(int l,int r){
  return (hsh[r] - (ll)hsh[l]*bpow[r-l]%MOD + MOD)%MOD;
}
int rolcmp(int al,int ar,int bl,int br){
  int alen = ar-al;
  int blen = br-bl;
  int len = min(alen,blen);
  int low = 0, high = len+1;
  while(low+1<high){
    int mid = (low+high)/2;
    if(subhash(al,al+mid)==subhash(bl,bl+mid)){
      low = mid;
    }else{
      high = mid;
    }
  }
  if(low < len){
    char a = s[al+low];
    char b = s[bl+low];
    return a-b;
  }else{
    return alen-blen;
  }
}

int sa[125252];

bool check(int x,int n,int k,int l){
  int head = 0;
  REP(_,k){
    // compare head~head+l, x~x+l
    if(head+l>n)return true;
    bool le = true;
    REP(j,l){
      char a = s[head+j];
      char b = s[x+j];
      if(a!=b){
        if(a<b)le=true;
        else le=false;
        break;
      }
    }
    if(le)head += l;
    else head += l-1;
  }
  return head>=n;
}

int main(){
  scanf("%d",&k);
  scanf("%s",s);
  n = strlen(s);
  // rolling hash
  hsh[0] = 0;
  REP(i,n)hsh[i+1] = ((ll)B*hsh[i] + s[i])%MOD;
  bpow[0] = 1;
  REP(i,n)bpow[i+1] = (ll)bpow[i]*B%MOD;

  // // suffix array
  // REP(i,n)sa[i]=i;
  // sort(sa,sa+n,[&](int x,int y){
  //   int cmp = rolcmp(x,n,y,n);
  //   return cmp<0;
  // });

  k++;
  int l = (n+k-1)/k;
  vi cand(n-l+1,0);
  REP(i,n-l+1)cand[i]=i;
  sort(ALL(cand),[&](int x,int y){
    int cmp = rolcmp(x,x+l,y,y+l);
    return cmp<0;
  });
  int low = -1, high = n-l+1-1;
  while(low+1<high){
    int mid = (low+high)/2;
    if(check(cand[mid],n,k,l)){
      high = mid;
    }else{
      low = mid;
    }
  }
  int ans = cand[high];
  REP(i,l)putchar(s[ans+i]);
  putchar('\n');
  return 0;
}

Submission Info

Submission Time
Task B - Problem where Commas Separate Digits
User rickytheta
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2773 Byte
Status AC
Exec Time 138 ms
Memory 1536 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:91:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k);
                 ^
./Main.cpp:92:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%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 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 384 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 4 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 4 ms 256 KB
subtask_04_06.txt AC 4 ms 256 KB
subtask_04_07.txt AC 4 ms 256 KB
subtask_04_08.txt AC 4 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 51 ms 1536 KB
subtask_05_02.txt AC 50 ms 1536 KB
subtask_05_03.txt AC 37 ms 1536 KB
subtask_05_04.txt AC 48 ms 1536 KB
subtask_05_05.txt AC 54 ms 1536 KB
subtask_05_06.txt AC 66 ms 1536 KB
subtask_05_07.txt AC 77 ms 1536 KB
subtask_05_08.txt AC 138 ms 1408 KB
subtask_05_09.txt AC 6 ms 1280 KB
subtask_05_10.txt AC 58 ms 1536 KB
subtask_05_11.txt AC 51 ms 1536 KB
subtask_05_12.txt AC 51 ms 1536 KB
subtask_05_13.txt AC 68 ms 1152 KB
subtask_05_14.txt AC 86 ms 1408 KB
subtask_05_15.txt AC 32 ms 768 KB