oj.uz

Submission #850025

# Submission time Handle Problem Language Result Execution time Memory
850025 2023-09-15T16:17:28 Z 1075508020060209tc Mađioničar (COI22_madionicar) C++14
25 / 100
 724 ms 25648 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<pair<int,int>,int>mp;
map<pair<int,int>,int>vis;
int ask(int l,int r){
if(vis[{l,r}]){return mp[{l,r}];}
cout<<"? "<<l<<" "<<r<<endl;
int ret;
vis[{l,r}]=1;
cin>>ret;
mp[{l,r}]=ret;
return ret;
}
int n;
int ar[200005];
int par[200005];
int tar[500005];
void rebuild(){
tar[1]=ar[1];
int it=2;
for(int i=2;i<=n;i++){
    tar[it]=2;
    tar[it+1]=ar[i];
    it+=2;
}
for(int i=1;i<=n+n-1;i++){
    ar[i]=tar[i];
}
}
int ps[500005];
int tme[500005];
int mod=1e9+7;
int hsh[500005];
int hsh2[500005];
int gthsh(int l,int r){
//cout<<l<<" "<<r<<endl;
int ret=(hsh[r]-hsh[l-1]+mod)%mod;
ret=(ret*tme[200000-r])%mod;
return ret;
}
int gthsh2(int l,int r){
//cout<<l<<" "<<r<<endl;
int ret=(hsh2[r]-hsh2[l-1]+mod)%mod;
ret=(ret*tme[200000-r])%mod;
return ret;
}
int typ;
int ok(int len){
if(typ==0){
    len=len*2;
}else{
    len=1+len*2;
}
if(len==0){return 1;}
for(int i=1;i<=n-len+1;i++){
    int v=gthsh(i,i+len-1);
    int vv=gthsh2(n-(i+len-1)+1,n-i+1);

    if(vv==v){
        return 1;
    }
}
return 0;

}


signed main(){
cin>>n;
for(int i=1;i<=n-1;i++){
    int v=ask(i,i+1);
    if(v==1){
        ar[i+1]=ar[i];
    }else{
        ar[i+1]=ar[i]^1;
    }
}
for(int i=1;i<=n;i++){
    tar[i]=ar[i];
   // cout<<ar[i]<<" ";
}//cout<<endl;
reverse(tar+1,tar+n+1);
tme[0]=1;
for(int i=1;i<=200000;i++){
    tme[i]=tme[i-1]*31%mod;
    hsh[i]=(hsh[i-1]+(ar[i]+1)*tme[i])%mod;
    hsh2[i]=(hsh2[i-1]+(tar[i]+1)*tme[i])%mod;
}/*
for(int i=1;i<=n;i++){
    cout<<hsh[i]<<" ";
}cout<<endl;
for(int i=1;i<=n;i++){
    cout<<hsh2[i]<<" ";
}cout<<endl;
for(int i=1;i<=n;i++){
    cout<<ar[i]<<" ";
}cout<<endl;
for(int i=1;i<=n;i++){
    cout<<tar[i]<<" ";
}cout<<endl;*/

int l=0;int r=n;
while(l<r){
    int mi=l+(r-l+1)/2;
    if(ok(mi)){
        l=mi;
    }else{
        r=mi-1;
    }
}
int ans=l*2;
l=0;r=n;
typ=1;
while(l<r){
    int mi=l+(r-l+1)/2;
    if(ok(mi)){
        l=mi;
    }else{
        r=mi-1;
    }
}
ans=max(l*2+1,ans);
cout<<"! "<<ans<<endl;return 0;





/*
rebuild();
int l;int r;
l=-1;r=-1;
par[1]=1;ar[n+n]=-1;
for(int i=2;i<=n+n-1;i++){
    if(r<i){
        int lit=i;int rit=i;
        par[i]=0;
        while(lit>=1&&rit<=n+n-1&&ar[lit]==ar[rit]){
            par[i]++;lit--;rit++;
        }
    }else{
        par[i]=min(par[l+r-i+1-1],r-i+1)-1;
        int lit=i-par[i];int rit=i+par[i];
        while(lit>=1&&rit<=n+n-1&&ar[lit]==ar[rit]){
            par[i]++;lit--;rit++;
        }
    }
    if(i+par[i]-1>r){
        l=i-par[i]+1;
        r=i+par[i]-1;
    }
}
int ans=0;
for(int i=1;i<=n+n-1;i++){
    ans=max(ans,par[i]);
    cout<<ar[i]<<" ";
}cout<<endl;
for(int i=1;i<=n+n-1;i++){
    cout<<par[i]<<" ";
}cout<<endl;
cout<<"! "<<ans<<endl;
*/
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12920 KB Output is correct
2 Incorrect 42 ms 12532 KB L = 207, expected 7
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12920 KB Output is correct
2 Incorrect 42 ms 12532 KB L = 207, expected 7
3 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 24892 KB Output is correct
2 Correct 642 ms 25648 KB Output is correct
3 Correct 639 ms 25448 KB Output is correct
4 Correct 599 ms 25072 KB Output is correct
5 Correct 646 ms 25264 KB Output is correct
6 Correct 634 ms 24816 KB Output is correct
7 Correct 625 ms 24708 KB Output is correct
8 Correct 679 ms 24860 KB Output is correct
9 Correct 713 ms 24868 KB Output is correct
10 Correct 708 ms 24772 KB Output is correct
11 Correct 584 ms 25496 KB Output is correct
12 Correct 597 ms 25152 KB Output is correct
13 Correct 654 ms 24920 KB Output is correct
14 Correct 670 ms 24928 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12920 KB Output is correct
2 Incorrect 42 ms 12532 KB L = 207, expected 7
3 Halted 0 ms 0 KB -