oj.uz

Submission #850235

# Submission time Handle Problem Language Result Execution time Memory
850235 2023-09-16T07:48:55 Z 1075508020060209tc Mađioničar (COI22_madionicar) C++14
38 / 100
 1231 ms 28356 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]=1;int lit=i-1;int rit=i+1;
        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]);
        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 136 ms 3768 KB Output is correct
2 Correct 77 ms 2552 KB Output is correct
3 Correct 73 ms 3004 KB Output is correct
4 Correct 115 ms 3780 KB Output is correct
5 Correct 120 ms 3904 KB Output is correct
6 Correct 108 ms 3780 KB Output is correct
7 Correct 128 ms 3708 KB Output is correct
8 Correct 142 ms 3428 KB Output is correct
9 Correct 124 ms 4328 KB Output is correct
10 Correct 83 ms 3180 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 3768 KB Output is correct
2 Correct 77 ms 2552 KB Output is correct
3 Correct 73 ms 3004 KB Output is correct
4 Correct 115 ms 3780 KB Output is correct
5 Correct 120 ms 3904 KB Output is correct
6 Correct 108 ms 3780 KB Output is correct
7 Correct 128 ms 3708 KB Output is correct
8 Correct 142 ms 3428 KB Output is correct
9 Correct 124 ms 4328 KB Output is correct
10 Correct 83 ms 3180 KB Output is correct
11 Correct 1155 ms 27568 KB Output is correct
12 Correct 798 ms 20144 KB Output is correct
13 Correct 792 ms 19360 KB Output is correct
14 Correct 1153 ms 28008 KB Output is correct
15 Correct 829 ms 21144 KB Output is correct
16 Correct 1231 ms 27248 KB Output is correct
17 Correct 1199 ms 27576 KB Output is correct
18 Correct 1083 ms 25920 KB Output is correct
19 Correct 1193 ms 27860 KB Output is correct
20 Correct 925 ms 23564 KB Output is correct
21 Correct 895 ms 22336 KB Output is correct
22 Correct 758 ms 20396 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1220 ms 28356 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 136 ms 3768 KB Output is correct
2 Correct 77 ms 2552 KB Output is correct
3 Correct 73 ms 3004 KB Output is correct
4 Correct 115 ms 3780 KB Output is correct
5 Correct 120 ms 3904 KB Output is correct
6 Correct 108 ms 3780 KB Output is correct
7 Correct 128 ms 3708 KB Output is correct
8 Correct 142 ms 3428 KB Output is correct
9 Correct 124 ms 4328 KB Output is correct
10 Correct 83 ms 3180 KB Output is correct
11 Correct 1155 ms 27568 KB Output is correct
12 Correct 798 ms 20144 KB Output is correct
13 Correct 792 ms 19360 KB Output is correct
14 Correct 1153 ms 28008 KB Output is correct
15 Correct 829 ms 21144 KB Output is correct
16 Correct 1231 ms 27248 KB Output is correct
17 Correct 1199 ms 27576 KB Output is correct
18 Correct 1083 ms 25920 KB Output is correct
19 Correct 1193 ms 27860 KB Output is correct
20 Correct 925 ms 23564 KB Output is correct
21 Correct 895 ms 22336 KB Output is correct
22 Correct 758 ms 20396 KB Output is correct
23 Runtime error 1220 ms 28356 KB Execution failed because the return code was nonzero
24 Halted 0 ms 0 KB -