oj.uz

Submission #850232

# Submission time Handle Problem Language Result Execution time Memory
850232 2023-09-16T07:45:39 Z 1075508020060209tc Mađioničar (COI22_madionicar) C++14
13 / 100
 1240 ms 28240 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 cnt=0;
int ask(int l,int r){
if(l==r){return 1;}
if(vis[{l,r}]){return mp[{l,r}];}
cnt++;
if(cnt==200001){
cout<<"! "<<7777777<<endl;
exit(12345); }
cout<<"? "<<l<<" "<<r<<endl;
int ret;
vis[{l,r}]=1;
cin>>ret;
mp[{l,r}]=ret;
return ret;
}
int n;
int rpl[300005];
int rask(int l,int r){
if(l==r){return 1;}
if(l%2==1){l++;}
if(r%2==1){r--;}
if(l==r){return 1;}
l=(l+1)/2;r=(r+1)/2;
return ask(l,r);
}

int par[300005];
//*#a#a#a#b#

signed main(){
cin>>n;

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


}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4504 KB Output is correct
2 Correct 95 ms 3368 KB Output is correct
3 Correct 77 ms 2700 KB Output is correct
4 Correct 195 ms 5260 KB Output is correct
5 Correct 179 ms 4992 KB Output is correct
6 Correct 149 ms 5040 KB Output is correct
7 Correct 236 ms 5876 KB Output is correct
8 Correct 190 ms 4780 KB Output is correct
9 Correct 223 ms 5260 KB Output is correct
10 Correct 97 ms 2852 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4504 KB Output is correct
2 Correct 95 ms 3368 KB Output is correct
3 Correct 77 ms 2700 KB Output is correct
4 Correct 195 ms 5260 KB Output is correct
5 Correct 179 ms 4992 KB Output is correct
6 Correct 149 ms 5040 KB Output is correct
7 Correct 236 ms 5876 KB Output is correct
8 Correct 190 ms 4780 KB Output is correct
9 Correct 223 ms 5260 KB Output is correct
10 Correct 97 ms 2852 KB Output is correct
11 Runtime error 1225 ms 28240 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1240 ms 28120 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4504 KB Output is correct
2 Correct 95 ms 3368 KB Output is correct
3 Correct 77 ms 2700 KB Output is correct
4 Correct 195 ms 5260 KB Output is correct
5 Correct 179 ms 4992 KB Output is correct
6 Correct 149 ms 5040 KB Output is correct
7 Correct 236 ms 5876 KB Output is correct
8 Correct 190 ms 4780 KB Output is correct
9 Correct 223 ms 5260 KB Output is correct
10 Correct 97 ms 2852 KB Output is correct
11 Runtime error 1225 ms 28240 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -