Submission #850025

#	Time	Username	Problem	Language	Result	Execution time	Memory
850025		1075508020060209tc	Mađioničar (COI22_madionicar)	C++14	25 / 100	724 ms	25648 KiB

Main

#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
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37