제출 #850030

#제출 시각아이디문제언어결과실행 시간메모리
8500301075508020060209tcMađioničar (COI22_madionicar)C++14
13 / 100
1300 ms26200 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; } 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; int ans=1; for(int i=1;i<=n;i++){ int l=1;int r=min(n-i+1,i); while(l<r){ int mi=l+(r-l+1)/2; int ll=i-mi+1;int rr=i+mi-1; if(mi==1||ask(ll,rr)){ l=mi; }else{ r=mi-1; } } ans=max(ans,l*2-1); l=0;r=min(i,n-i); while(l<r){ int mi=l+(r-l+1)/2; int ll=i-mi+1;int rr=i+mi; if(mi==0||ask(ll,rr)){ l=mi; }else{ r=mi-1; } } ans=max(ans,l*2); } 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...