이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
}
}
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++){
cout<<ar[i]<<" ";
}cout<<endl;*/
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);
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |