Submission #849981

#TimeUsernameProblemLanguageResultExecution timeMemory
8499811075508020060209tcMađioničar (COI22_madionicar)C++14
0 / 100
573 ms16580 KiB
#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; } } 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; } } rebuild(); int l;int r; l=-1;r=-1; par[1]=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&&ar[lit]==ar[rit]){ par[i]++;lit--;rit++; } }else{ par[i]=par[l+r-i+1-1]; int lit=i-par[i];int rit=i+par[i]; while(lit>=1&&rit<=n&&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<<"! "<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...