Submission #5555422
Source Code Expand
#include<bits/stdc++.h> using namespace std; using Int = long long; struct SuffixArray{ string s; vector<int> sa,rev; SuffixArray(){} SuffixArray(const string &S):s(S){ int n=s.size(); s.push_back('$'); sa.resize(n+1); iota(sa.begin(),sa.end(),0); sort(sa.begin(),sa.end(), [&](int a,int b){ if(s[a]==s[b]) return a>b; return s[a]<s[b]; }); vector<int> c(n+1,0),r(n+1),cnt(n+1); for(int i=0;i<=n;i++) r[i]=s[i]; for(int len=1;len<=n;len*=2){ for(int i=0;i<=n;i++){ c[sa[i]]=i; if(i>0 && r[sa[i-1]]==r[sa[i]] && sa[i-1]+len<=n && r[sa[i-1]+len/2]==r[sa[i]+len/2]) c[sa[i]]=c[sa[i-1]]; } iota(cnt.begin(),cnt.end(),0); copy(sa.begin(),sa.end(),r.begin()); for(int i=0;i<=n;i++){ int s1=r[i]-len; if(s1>=0) sa[cnt[c[s1]]++]=s1; } c.swap(r); } rev.resize(n+1); for(int i=0;i<=n;i++) rev[sa[i]]=i; } int operator[](int i) const{return sa[i];} bool lt_substr(string &t,int si,int ti){ int sn=s.size(),tn=t.size(); while(si<sn&&ti<tn){ if(s[si]<t[ti]) return 1; if(s[si]>t[ti]) return 0; si++;ti++; } return si==sn&&ti<tn; } int lower_bound(string& t){ int l=0,r=s.size(); while(l+1<r){ int m=(l+r)>>1; if(lt_substr(t,sa[m],0)) l=m; else r=m; } return r; } int upper_bound(string& t){ t.back()++; int res=lower_bound(t); t.back()--; return res; } // O(|T|*log|S|) int count(string& T){ return upper_bound(T)-lower_bound(T); } }; //BEGIN CUT HERE struct LongestCommonPrefix{ SuffixArray sa; vector<int> lcp,ht; vector<vector<int> > dat; LongestCommonPrefix(string &s):sa(s){ int n=s.size(); lcp.assign(n,0); int t=0; lcp[0]=0; for(int i=0;i<n;i++){ int j=sa[sa.rev[i]-1]; if(t>0) t--; for(;j+t<n&&i+t<n;t++){ if(sa.s[j+t]!=sa.s[i+t]) break; } lcp[sa.rev[i]-1]=t; } int h=1; while((1<<h)<n) h++; dat.assign(h,vector<int>(n)); ht.assign(n+1,0); for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1; for(int j=0;j<n;j++) dat[0][j]=lcp[j]; for(int i=1,p=1;i<h;i++,p<<=1) for(int j=0;j<n;j++) dat[i][j]=min(dat[i-1][j],dat[i-1][min(j+p,n-1)]); } int query(int a,int b){ a=sa.rev[a];b=sa.rev[b]; if(a>b) swap(a,b); int l=b-a; return min(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]); } }; //END CUT HERE //INSERT ABOVE HERE signed ARC060_F(){ cin.tie(0); ios::sync_with_stdio(0); string s; cin>>s; int n=s.size(); { string t(s); t.erase(unique(t.begin(),t.end()),t.end()); if(t.size()==1u){ cout<<n<<endl<<1<<endl; return 0; } } vector<vector<int> > v(n+1); for(int i=1;i<=n;i++) for(int j=i+i;j<=n;j+=i) v[j].emplace_back(i); LongestCommonPrefix lcp(s); auto check= [&](int l,int r)->int{ for(int x:v[r-l]) if(lcp.query(l,l+x)>=r-l-x) return 0; return 1; }; if(check(0,n)){ cout<<1<<endl<<1<<endl; return 0; } int ans=0; for(int i=1;i<n;i++) ans+=check(0,i)&&check(i,n); cout<<2<<endl<<ans<<endl; return 0; } /* verified on 2019/05/23 https://beta.atcoder.jp/contests/arc060/tasks/arc060_d */ signed main(){ ARC060_F(); return 0; };
Submission Info
Submission Time | |
---|---|
Task | F - Best Representation |
User | beet |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 3607 Byte |
Status | AC |
Exec Time | 1475 ms |
Memory | 103748 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | example_01.txt, example_02.txt, example_03.txt |
Subtask1 | example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt |
All | example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
example_01.txt | AC | 1 ms | 256 KB |
example_02.txt | AC | 1 ms | 256 KB |
example_03.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 2 ms | 384 KB |
subtask1_04.txt | AC | 1 ms | 256 KB |
subtask1_05.txt | AC | 3 ms | 896 KB |
subtask1_06.txt | AC | 3 ms | 896 KB |
subtask1_07.txt | AC | 1 ms | 256 KB |
subtask1_08.txt | AC | 3 ms | 896 KB |
subtask1_09.txt | AC | 3 ms | 896 KB |
subtask1_10.txt | AC | 3 ms | 896 KB |
subtask1_11.txt | AC | 3 ms | 896 KB |
subtask1_12.txt | AC | 3 ms | 896 KB |
subtask1_13.txt | AC | 4 ms | 896 KB |
subtask1_14.txt | AC | 4 ms | 896 KB |
subtask1_15.txt | AC | 1 ms | 256 KB |
subtask1_16.txt | AC | 1 ms | 256 KB |
subtask1_17.txt | AC | 1 ms | 256 KB |
subtask1_18.txt | AC | 1 ms | 256 KB |
subtask1_19.txt | AC | 3 ms | 896 KB |
subtask1_20.txt | AC | 3 ms | 896 KB |
subtask1_21.txt | AC | 3 ms | 896 KB |
subtask1_22.txt | AC | 3 ms | 896 KB |
subtask1_23.txt | AC | 3 ms | 896 KB |
subtask1_24.txt | AC | 3 ms | 896 KB |
subtask1_25.txt | AC | 3 ms | 896 KB |
subtask1_26.txt | AC | 3 ms | 896 KB |
subtask1_27.txt | AC | 3 ms | 896 KB |
subtask1_28.txt | AC | 3 ms | 896 KB |
subtask1_29.txt | AC | 3 ms | 896 KB |
subtask1_30.txt | AC | 3 ms | 896 KB |
subtask1_31.txt | AC | 4 ms | 896 KB |
subtask1_32.txt | AC | 4 ms | 896 KB |
subtask1_33.txt | AC | 4 ms | 896 KB |
subtask2_01.txt | AC | 863 ms | 79636 KB |
subtask2_02.txt | AC | 3 ms | 1308 KB |
subtask2_03.txt | AC | 667 ms | 101588 KB |
subtask2_04.txt | AC | 659 ms | 101588 KB |
subtask2_05.txt | AC | 3 ms | 1308 KB |
subtask2_06.txt | AC | 701 ms | 101828 KB |
subtask2_07.txt | AC | 672 ms | 101828 KB |
subtask2_08.txt | AC | 880 ms | 101828 KB |
subtask2_09.txt | AC | 1174 ms | 101828 KB |
subtask2_10.txt | AC | 1164 ms | 101828 KB |
subtask2_11.txt | AC | 1190 ms | 101828 KB |
subtask2_12.txt | AC | 1475 ms | 101828 KB |
subtask2_13.txt | AC | 768 ms | 101828 KB |
subtask2_14.txt | AC | 679 ms | 101828 KB |
subtask2_15.txt | AC | 783 ms | 103748 KB |
subtask2_16.txt | AC | 681 ms | 101828 KB |
subtask2_17.txt | AC | 716 ms | 101828 KB |
subtask2_18.txt | AC | 744 ms | 101828 KB |
subtask2_19.txt | AC | 809 ms | 101828 KB |
subtask2_20.txt | AC | 813 ms | 101828 KB |
subtask2_21.txt | AC | 776 ms | 94232 KB |
subtask2_22.txt | AC | 1076 ms | 101700 KB |
subtask2_23.txt | AC | 1024 ms | 101700 KB |
subtask2_24.txt | AC | 995 ms | 85792 KB |
subtask2_25.txt | AC | 965 ms | 90488 KB |
subtask2_26.txt | AC | 1147 ms | 96524 KB |
subtask2_27.txt | AC | 871 ms | 82176 KB |
subtask2_28.txt | AC | 312 ms | 51716 KB |
subtask2_29.txt | AC | 743 ms | 79628 KB |