test/aoj/3033.test.cpp

• View this file on GitHub
• Last update: 2023-03-20 15:38:36+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3033

Depends on

• Suffix Array (string/suffixarray.cpp)

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3033

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../string/suffixarray.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using ll = long long;
  int n;
  ll k;
  string s;
  cin>>n>>k>>s;

  auto calc=[](ll x){return x*(x+1)/2;};
  ll zs=0;
  vector<ll> cnt(n+1,1);
  for(int i=0;i<n;i++){
    if(s[i]=='0'){
      if(i+1>=n||s[i+1]!='0') zs+=calc(cnt[i]);
      if(i+1<n) cnt[i+1]+=cnt[i];
      cnt[i]=0;
    }
  }

  if(k<=zs){
    cout<<0<<endl;
    return 0;
  }
  k-=zs+1;

  vector<ll> sum(n+1,0);
  for(int i=0;i<n;i++) sum[i+1]=sum[i]+cnt[i];

  int len=1;
  while(k>=sum[n+1-len]&&len<n) k-=sum[n+1-(len++)];

  SuffixArray sa(s);
  int pos=0;
  for(int i=1;i<=n;i++){
    if(s[sa.sa[i]]=='0'||sa.sa[i]+len>n) continue;
    if(k>=0) pos=sa.sa[i];
    k-=cnt[sa.sa[i]];
  }

  cout<<s.substr(pos,len)<<endl;
  return 0;
}

#line 1 "test/aoj/3033.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3033

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "string/suffixarray.cpp"

#line 3 "string/suffixarray.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename Seq = string>
struct SuffixArray{
  const Seq s;
  vector<int> sa,rev;

  SuffixArray(const Seq &s_):s(s_){

    int n=s.size();
    auto cmp=[&](int a,int b){
      if(a==b) return false;
      if(a==n) return true;
      if(b==n) return false;
      if(s[a]==s[b]) return a>b;
      return s[a]<s[b];
    };

    sa.resize(n+1);
    iota(sa.begin(),sa.end(),0);
    sort(sa.begin(),sa.end(),cmp);

    vector<int> rs(n+1);
    {
      Seq t(s);
      sort(t.begin(),t.end());
      t.erase(unique(t.begin(),t.end()),t.end());
      for(int i=0;i<n;i++)
        rs[i]=std::lower_bound(t.begin(),t.end(),s[i])-t.begin();
      rs[n]=0;
    }

    for(int len=1;len<=n;len*=2){
      vector<int> cs(n+1);
      for(int i=0;i<=n;i++){
        cs[sa[i]]=i;
        if(i==0) continue;
        if(rs[sa[i-1]]!=rs[sa[i]]) continue;
        if(sa[i-1]+len>=n) continue;
        if(rs[sa[i-1]+len/2]!=rs[sa[i]+len/2]) continue;
        cs[sa[i]]=cs[sa[i-1]];
      }
      vector<int> cnt(n+1);
      iota(cnt.begin(),cnt.end(),0);
      copy(sa.begin(),sa.end(),rs.begin());
      for(int i=0;i<=n;i++){
        int s1=rs[i]-len;
        if(s1>=0) sa[cnt[cs[s1]]++]=s1;
      }
      cs.swap(rs);
    }
    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(const Seq &t,int si,int ti){
    int sn=s.size(),tn=t.size();
    while(si<sn and ti<tn){
      if(s[si]<t[ti]) return 1;
      if(s[si]>t[ti]) return 0;
      si++;ti++;
    }
    return si==sn and ti<tn;
  }

  int lower_bound(Seq t){
    int l=0,r=s.size()+1;
    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(Seq t){
    t.back()++;
    int res=lower_bound(t);
    t.back()--;
    return res;
  }

  // O(|t| \log|s|)
  int count(Seq t){
    return upper_bound(t)-lower_bound(t);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  vector<int> vs({1, 2, 3, 1, 2, 1});
  SuffixArray sa(vs);
  for(int i=0;i<=(int)vs.size();i++) cout<<sa[i]<<endl;

  cout<<sa.count({1})<<endl;
  cout<<sa.count({1, 2})<<endl;
  cout<<sa.count({1, 2, 3})<<endl;
  cout<<sa.count({1, 2, 3, 4})<<endl;
  return 0;
}
#endif
#line 8 "test/aoj/3033.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using ll = long long;
  int n;
  ll k;
  string s;
  cin>>n>>k>>s;

  auto calc=[](ll x){return x*(x+1)/2;};
  ll zs=0;
  vector<ll> cnt(n+1,1);
  for(int i=0;i<n;i++){
    if(s[i]=='0'){
      if(i+1>=n||s[i+1]!='0') zs+=calc(cnt[i]);
      if(i+1<n) cnt[i+1]+=cnt[i];
      cnt[i]=0;
    }
  }

  if(k<=zs){
    cout<<0<<endl;
    return 0;
  }
  k-=zs+1;

  vector<ll> sum(n+1,0);
  for(int i=0;i<n;i++) sum[i+1]=sum[i]+cnt[i];

  int len=1;
  while(k>=sum[n+1-len]&&len<n) k-=sum[n+1-(len++)];

  SuffixArray sa(s);
  int pos=0;
  for(int i=1;i<=n;i++){
    if(s[sa.sa[i]]=='0'||sa.sa[i]+len>n) continue;
    if(k>=0) pos=sa.sa[i];
    k-=cnt[sa.sa[i]];
  }

  cout<<s.substr(pos,len)<<endl;
  return 0;
}

Back to top page