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