Submission #5555118


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){
    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(lcp.sa.rev[l],lcp.sa.rev[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 2018/05/10
  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 3605 Byte
Status AC
Exec Time 1328 ms
Memory 103748 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 500 / 500
Status
AC × 3
AC × 36
AC × 65
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 4 ms 896 KB
subtask1_12.txt AC 3 ms 896 KB
subtask1_13.txt AC 3 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 735 ms 79636 KB
subtask2_02.txt AC 3 ms 1308 KB
subtask2_03.txt AC 577 ms 101588 KB
subtask2_04.txt AC 581 ms 101588 KB
subtask2_05.txt AC 3 ms 1308 KB
subtask2_06.txt AC 590 ms 101828 KB
subtask2_07.txt AC 594 ms 101828 KB
subtask2_08.txt AC 876 ms 101828 KB
subtask2_09.txt AC 1069 ms 101828 KB
subtask2_10.txt AC 1125 ms 101828 KB
subtask2_11.txt AC 1120 ms 101828 KB
subtask2_12.txt AC 1328 ms 101828 KB
subtask2_13.txt AC 669 ms 101828 KB
subtask2_14.txt AC 647 ms 101828 KB
subtask2_15.txt AC 692 ms 103748 KB
subtask2_16.txt AC 588 ms 101828 KB
subtask2_17.txt AC 592 ms 101828 KB
subtask2_18.txt AC 647 ms 101828 KB
subtask2_19.txt AC 776 ms 101828 KB
subtask2_20.txt AC 747 ms 101828 KB
subtask2_21.txt AC 744 ms 94232 KB
subtask2_22.txt AC 1014 ms 101700 KB
subtask2_23.txt AC 980 ms 101700 KB
subtask2_24.txt AC 936 ms 85792 KB
subtask2_25.txt AC 929 ms 90488 KB
subtask2_26.txt AC 1092 ms 96524 KB
subtask2_27.txt AC 821 ms 82176 KB
subtask2_28.txt AC 331 ms 51716 KB
subtask2_29.txt AC 716 ms 79628 KB