Submission #829169

# Submission time Handle Problem Language Result Execution time Memory
829169 2023-08-18T05:55:48 Z 1075508020060209tc Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
187 ms 1108 KB
#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int LN=10;
int n;int m;
int ar[6010];int br[6010];int rb[6010];
void init(){
string s;
cin>>s;
n=s.size();
s="*"+s;
for(int i=1;i<=n;i++){
    ar[i]=s[i]-'a'+1;
   // ar[i]=ar[i]*(ar[i]+3);
   // ar[i+n]=ar[i];
}
cin>>s;
m=s.size();
s="*"+s;
for(int i=1;i<=m;i++){
    br[i]=s[i]-'a'+1;
   // br[i]=br[i]*(br[i]+3);
    //br[i+m]=br[i];
}
for(int i=1;i<=m;i++){
    rb[i]=br[i];
}
reverse(rb+1,rb+m+1);
}
int psa[200][3010];int psb[200][3010];
int pssa[200][3010];int pssb[200][3010];
int pxa[200][3010];int pxb[200][3010];
int psrb[200][3010];
int pssrb[200][3010];
int pxrb[200][3010];
void precalc(int len){
    for(int i=1;i+len-1<=n;i++){
        int v=ar[i];
        for(int j=2;j<=len;j++){
            v=v*27+ar[i+j-1];
            v%=mod;
        }
        psa[len][i]=(psa[len][i-1]+v)%mod;
        pssa[len][i]=(pssa[len][i-1]+v*v)%mod;
        pxa[len][i]=pxa[len][i-1]^v;
    }
    for(int i=1;i+len-1<=m;i++){
        int v=br[i];
        for(int j=2;j<=len;j++){
            v=v*27+br[i+j-1];
            v%=mod;
        }
        psb[len][i]=(psb[len][i-1]+v)%mod;
        pssb[len][i]=(pssb[len][i-1]+v*v)%mod;
        pxb[len][i]=pxb[len][i-1]^v;
    }
    for(int i=1;i+len-1<=m;i++){
        int v=rb[i];
        for(int j=2;j<=len;j++){
            v=v*27+rb[i+j-1];
            v%=mod;
        }
        psrb[len][i]=(psrb[len][i-1]+v)%mod;
        pssrb[len][i]=(pssrb[len][i-1]+v*v)%mod;
        pxrb[len][i]=pxrb[len][i-1]^v;
    }
}
 
int cyc(int l,int r,int st,int len){
    int ret=ar[st];
    for(int i=2;i<=len;i++){
        st++;
        if(st==r+1){st=l;}
        ret=ret*27+ar[st];
        ret%=mod;
    }
    return ret;
}
int cycb(int l,int r,int st,int len){
    int ret=br[st];
    for(int i=2;i<=len;i++){
        st++;
        if(st==r+1){st=l;}
        ret=ret*27+br[st];
        ret%=mod;
    }
    return ret;
}
int cycrb(int l,int r,int st,int len){
    int ret=rb[st];
    for(int i=2;i<=len;i++){
        st++;
        if(st==r+1){st=l;}
        ret=ret*27+rb[st];
        ret%=mod;
    }
    return ret;
}
 
int ansa;int ansb;
int ok(int mi){
map<vector<array<int,3>>,int>mp;
for(int i=1;i<=n-mi+1;i++){
    vector<array<int,3>>vc;
    int l=i;int r=i+mi-1;
    for(int len=1;len<=LN;len++){
        array<int,3>tar;
        tar[0]=0;tar[1]=0;tar[2]=0;
        if(r-len+1>=l){
            tar[0]=(psa[len][r-len+1]-psa[len][l-1]+mod)%mod;
            tar[1]=(pssa[len][r-len+1]-pssa[len][l-1]+mod)%mod;
            tar[2]=pxa[len][r-len+1]^pxa[len][l-1];
        }
        for(int j=max(l,r-len+1+1);j<=r;j++){
            int v=cyc(l,r,j,len);
            tar[0]=(tar[0]+v)%mod;
            tar[1]=(tar[1]+v*v)%mod;
            tar[2]=tar[2]^v;
        }
      //  cout<<i<<" "<<tar[0]<<" "<<tar[1]<<" "<<tar[2]<<endl;
        vc.push_back(tar);
    }
    //sort(vc.begin(),vc.end());
    mp[vc]=i;
}
for(int i=1;i<=m-mi+1;i++){
    vector<array<int,3>>vc;
    int l=i;int r=i+mi-1;
    for(int len=1;len<=LN;len++){
        array<int,3>tar;
        tar[0]=0;tar[1]=0;tar[2]=0;
        if(r-len+1>=l){
            tar[0]=(psb[len][r-len+1]-psb[len][l-1]+mod)%mod;
            tar[1]=(pssb[len][r-len+1]-pssb[len][l-1]+mod)%mod;
            tar[2]=pxb[len][r-len+1]^pxb[len][l-1];
        }
        for(int j=max(l,r-len+1+1);j<=r;j++){
            int v=cycb(l,r,j,len);
            tar[0]=(tar[0]+v)%mod;
            tar[1]=(tar[1]+v*v)%mod;
            tar[2]=tar[2]^v;
        }
        vc.push_back(tar);
    }
    //sort(vc.begin(),vc.end());
    if(mp[vc]>=1){
        ansa=mp[vc];
        ansb=i;
        return 1;
    }
}
for(int i=1;i<=m-mi+1;i++){
    vector<array<int,3>>vc;
    int l=i;int r=i+mi-1;
    for(int len=1;len<=LN;len++){
        array<int,3>tar;
        tar[0]=0;tar[1]=0;tar[2]=0;
        if(r-len+1>=l){
            tar[0]=(psrb[len][r-len+1]-psrb[len][l-1]+mod)%mod;
            tar[1]=(pssrb[len][r-len+1]-pssrb[len][l-1]+mod)%mod;
            tar[2]=pxrb[len][r-len+1]^pxrb[len][l-1];
        }
        for(int j=max(l,r-len+1+1);j<=r;j++){
            int v=cycrb(l,r,j,len);
            tar[0]=(tar[0]+v)%mod;
            tar[1]=(tar[1]+v*v)%mod;
            tar[2]=tar[2]^v;
        }
        vc.push_back(tar);
    }
    //sort(vc.begin(),vc.end());
    if(mp[vc]>=1){
        ansa=mp[vc];
        ansb=m-(i+mi-1)+1;
        return 1;
    }
}
return 0;
}
 
signed main()
{
    init();
    for(int i=1;i<=LN;i++){
        precalc(i);
    }/*
    for(int i=1;i<=n;i++){
        cout<<ar[i]<<" ";
    }cout<<endl;
*/
  //  ok(1);return 0;
 
    int l=0;int r=n;
    for(int i=1;i<=n;i++){
        if(ok(i)){l=i;}//else{break; }
    }
    cout<<l<<endl;
    ok(l);
    cout<<ansa-1<<" "<<ansb-1<<endl;
 
}

Compilation message

necklace.cpp:1:63: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")
      |                                                               ^
necklace.cpp:1:63: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
necklace.cpp:9:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
    9 | void init(){
      |           ^
necklace.cpp:9:11: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:38:21: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   38 | void precalc(int len){
      |                     ^
necklace.cpp:38:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:71:35: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   71 | int cyc(int l,int r,int st,int len){
      |                                   ^
necklace.cpp:71:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:81:36: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   81 | int cycb(int l,int r,int st,int len){
      |                                    ^
necklace.cpp:81:36: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:91:37: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   91 | int cycrb(int l,int r,int st,int len){
      |                                     ^
necklace.cpp:91:37: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:103:14: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
  103 | int ok(int mi){
      |              ^
necklace.cpp:103:14: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp:183:13: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
  183 | signed main()
      |             ^
necklace.cpp:183:13: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
necklace.cpp: In function 'int main()':
necklace.cpp:195:17: warning: unused variable 'r' [-Wunused-variable]
  195 |     int l=0;int r=n;
      |                 ^
# Verdict Execution time Memory Grader output
1 Correct 9 ms 724 KB Output is correct
2 Correct 8 ms 792 KB Output is correct
3 Correct 11 ms 792 KB Output is correct
4 Correct 12 ms 724 KB Output is correct
5 Correct 18 ms 852 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 724 KB Output is correct
2 Correct 8 ms 792 KB Output is correct
3 Correct 11 ms 792 KB Output is correct
4 Correct 12 ms 724 KB Output is correct
5 Correct 18 ms 852 KB Output is correct
6 Correct 157 ms 1020 KB Output is correct
7 Correct 140 ms 1028 KB Output is correct
8 Incorrect 187 ms 1108 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 724 KB Output is correct
2 Correct 8 ms 792 KB Output is correct
3 Correct 11 ms 792 KB Output is correct
4 Correct 12 ms 724 KB Output is correct
5 Correct 18 ms 852 KB Output is correct
6 Correct 157 ms 1020 KB Output is correct
7 Correct 140 ms 1028 KB Output is correct
8 Incorrect 187 ms 1108 KB Output isn't correct
9 Halted 0 ms 0 KB -