Submission #1807743
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} class SuffixArray{ void create_begin_bucket(vector<int>&v,vector<int>&bucket){ fill(bucket.begin(),bucket.end(),0); for(int i=0;i<v.size();i++)bucket[v[i]]++; int sum=0; for(int i=0;i<bucket.size();i++){bucket[i]+=sum;swap(sum,bucket[i]);} } void create_end_bucket(vector<int>&v,vector<int>&bucket){ fill(bucket.begin(),bucket.end(),0); for(int i=0;i<v.size();i++)bucket[v[i]]++; for(int i=1;i<bucket.size();i++)bucket[i]+=bucket[i-1]; } void induced_sort(vector<int>&v,vector<int>&sa,int mv,vector<int>&bucket,vector<int>&is_l){ create_begin_bucket(v,bucket); for(int i=0;i<v.size();i++)if(sa[i]>0&&is_l[sa[i]-1])sa[bucket[v[sa[i]-1]]++]=sa[i]-1; } void invert_induced_sort(vector<int>&v,vector<int>&sa,int mv,vector<int>&bucket,vector<int>&is_l){ create_end_bucket(v,bucket); for(int i=v.size()-1;i>=0;i--)if(sa[i]>0&&!is_l[sa[i]-1])sa[--bucket[v[sa[i]-1]]]=sa[i]-1; } vector<int>sa_is(vector<int>v,int mv){ if(v.size()==1)return vector<int>(1,0); vector<int>is_l(v.size()); vector<int>bucket(mv+1); vector<int>sa(v.size(),-1); auto is_lms=[&](int x)->bool{return x>0&&is_l[x-1]&&!is_l[x];}; is_l[v.size()-1]=0; for(int i=v.size()-2;i>=0;i--)is_l[i]=v[i]>v[i+1]||(v[i]==v[i+1]&&is_l[i+1]); create_end_bucket(v,bucket); for(int i=0;i<v.size();i++)if(is_lms(i))sa[--bucket[v[i]]]=i; induced_sort(v,sa,mv,bucket,is_l); invert_induced_sort(v,sa,mv,bucket,is_l); int cur=0; vector<int>order(v.size()); for(int i=0;i<v.size();i++)if(is_lms(i))order[i]=cur++; vector<int>next_v(cur); cur=-1; int prev=-1; for(int i=0;i<v.size();i++){ if(!is_lms(sa[i]))continue; bool diff=false; for(int d=0;d<v.size();d++){ if(prev==-1||v[sa[i]+d]!=v[prev+d]||is_l[sa[i]+d]!=is_l[prev+d]){ diff=true; break; } else if(d>0&&is_lms(sa[i]+d))break; } if(diff){cur++;prev=sa[i];} next_v[order[sa[i]]]=cur; } vector<int>re_order(next_v.size()); for(int i=0;i<v.size();i++)if(is_lms(i))re_order[order[i]]=i; vector<int>next_sa=sa_is(next_v,cur); create_end_bucket(v,bucket); for(int i=0;i<sa.size();i++)sa[i]=-1; for(int i=next_sa.size()-1;i>=0;i--)sa[--bucket[v[re_order[next_sa[i]]]]]=re_order[next_sa[i]]; induced_sort(v,sa,mv,bucket,is_l); invert_induced_sort(v,sa,mv,bucket,is_l); return sa; } void sa_is(string &s){ vector<int>v(s.size()+1); for(int i=0;i<s.size();i++)v[i]=s[i]; sa=sa_is(v,*max_element(v.begin(),v.end())); } void construct_lcp(){ lcp.resize(s.size()); rank.resize(s.size()+1); int n=s.size(); for(int i=0;i<=n;i++)rank[sa[i]]=i; int h=0; lcp[0]=0; for(int i=0;i<n;i++){ int j=sa[rank[i]-1]; if(h>0)h--; for(;j+h<n&&i+h<n;h++){ if(s[j+h]!=s[i+h])break; } lcp[rank[i]-1]=h; } } struct segtree{ int N; vector<int>dat; void init(vector<int> &v){ for(N=1;N<v.size();N<<=1); dat.resize(N*2,1001001001); for(int i=0;i<v.size();i++)dat[i+N-1]=v[i]; for(int i=N-2;i>=0;i--)dat[i]=min(dat[i*2+1],dat[i*2+2]); } int get_min(int a,int b,int k,int l,int r){ if(r<=a||b<=l)return 1001001001; if(a<=l&&r<=b)return dat[k]; return min(get_min(a,b,k*2+1,l,(l+r)/2),get_min(a,b,k*2+2,(l+r)/2,r)); } int get_min(int a,int b){return get_min(a,b,0,0,N);} }; class sparse_table{ vector<vector<int> >st; public: void init(vector<int>vec){ int b; for(b=0;(1<<b)<=vec.size();b++); st.assign(b,vector<int>(1<<b)); for(int i=0;i<vec.size();i++)st[0][i]=vec[i]; for(int i=1;i<b;i++){ for(int j=0;j+(1<<i)<=(1<<b);j++){ st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]); } } } int get_min(int l,int r){ assert(l<r); int b=32-__builtin_clz(r-l)-1; return min(st[b][l],st[b][r-(1<<b)]); } sparse_table(){} sparse_table(vector<int>vec){init(vec);} }; public: sparse_table st; string s; vector<int>sa,lcp,rank; void init(string &t){ s=t; sa_is(s); construct_lcp(); st.init(lcp); } SuffixArray(string &t){init(t);} SuffixArray(){} bool contain(string &t){ int lb=0,ub=s.size(); while(ub-lb>1){ int mid=(lb+ub)/2; if(s.compare(sa[mid],t.size(),t)<0)lb=mid; else ub=mid; } return s.compare(sa[ub],t.size(),t)==0; } int get_lcp(int i,int j){ assert(i!=j); if(rank[i]>rank[j])swap(i,j); return st.get_min(rank[i],rank[j]); } int operator[](const int idx)const{ return sa[idx]; } }; signed main(){ int K; string S; cin>>K>>S; K++; int L=S.size(); S+=string(S.size(),'9'+1); int x=(L+K-1)/K; SuffixArray sa(S); int lb=0,ub=L; while(ub-lb>1){ int mid=(ub+lb)/2; int cnt=0; int pos=0; while(pos<L){ if(sa.rank[pos]<=mid)pos+=x; else pos+=x-1; cnt++; } if(cnt<=K)ub=mid; else lb=mid; } while(sa.sa[ub]+x>L)ub++; cout<<S.substr(sa.sa[ub],x)<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | latte0119 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 6470 Byte |
Status | TLE |
Exec Time | 3162 ms |
Memory | 45868 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 0 / 100 | 0 / 200 | 0 / 200 | 0 / 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 | 1 ms | 256 KB |
subtask_01_02.txt | TLE | 3155 ms | 256 KB |
subtask_01_03.txt | TLE | 3155 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 | TLE | 3155 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 | TLE | 3155 ms | 256 KB |
subtask_01_14.txt | AC | 1 ms | 256 KB |
subtask_01_15.txt | TLE | 3155 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 | TLE | 3155 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 | TLE | 3155 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 | TLE | 3155 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 | 2 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 | 768 KB |
subtask_04_02.txt | AC | 2 ms | 768 KB |
subtask_04_03.txt | TLE | 3155 ms | 768 KB |
subtask_04_04.txt | AC | 2 ms | 768 KB |
subtask_04_05.txt | AC | 2 ms | 768 KB |
subtask_04_06.txt | AC | 2 ms | 768 KB |
subtask_04_07.txt | AC | 2 ms | 768 KB |
subtask_04_08.txt | AC | 2 ms | 768 KB |
subtask_04_09.txt | AC | 2 ms | 768 KB |
subtask_04_10.txt | AC | 2 ms | 768 KB |
subtask_04_11.txt | AC | 2 ms | 768 KB |
subtask_04_12.txt | AC | 2 ms | 768 KB |
subtask_04_13.txt | AC | 2 ms | 512 KB |
subtask_04_14.txt | AC | 1 ms | 384 KB |
subtask_04_15.txt | AC | 2 ms | 768 KB |
subtask_05_01.txt | AC | 63 ms | 45852 KB |
subtask_05_02.txt | AC | 62 ms | 45840 KB |
subtask_05_03.txt | TLE | 3162 ms | 45844 KB |
subtask_05_04.txt | AC | 60 ms | 45844 KB |
subtask_05_05.txt | AC | 60 ms | 45852 KB |
subtask_05_06.txt | AC | 60 ms | 45852 KB |
subtask_05_07.txt | AC | 60 ms | 45848 KB |
subtask_05_08.txt | AC | 57 ms | 45844 KB |
subtask_05_09.txt | AC | 58 ms | 45848 KB |
subtask_05_10.txt | AC | 59 ms | 45868 KB |
subtask_05_11.txt | AC | 51 ms | 45868 KB |
subtask_05_12.txt | AC | 50 ms | 45868 KB |
subtask_05_13.txt | AC | 52 ms | 44172 KB |
subtask_05_14.txt | AC | 57 ms | 45432 KB |
subtask_05_15.txt | AC | 26 ms | 21564 KB |