oj.uz

Submission #850231

# Submission time Handle Problem Language Result Execution time Memory
850231 2023-09-16T07:43:44 Z 1075508020060209tc Mađioničar (COI22_madionicar) C++14
13 / 100
 1236 ms 28244 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 ask(int l,int r){
if(l==r){return 1;}
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 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 156 ms 4376 KB Output is correct
2 Correct 91 ms 3152 KB Output is correct
3 Correct 97 ms 2736 KB Output is correct
4 Correct 206 ms 5608 KB Output is correct
5 Correct 180 ms 5168 KB Output is correct
6 Correct 139 ms 4436 KB Output is correct
7 Correct 221 ms 5576 KB Output is correct
8 Correct 174 ms 4852 KB Output is correct
9 Correct 222 ms 5508 KB Output is correct
10 Correct 89 ms 3152 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 4376 KB Output is correct
2 Correct 91 ms 3152 KB Output is correct
3 Correct 97 ms 2736 KB Output is correct
4 Correct 206 ms 5608 KB Output is correct
5 Correct 180 ms 5168 KB Output is correct
6 Correct 139 ms 4436 KB Output is correct
7 Correct 221 ms 5576 KB Output is correct
8 Correct 174 ms 4852 KB Output is correct
9 Correct 222 ms 5508 KB Output is correct
10 Correct 89 ms 3152 KB Output is correct
11 Runtime error 1229 ms 28244 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1236 ms 28072 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 4376 KB Output is correct
2 Correct 91 ms 3152 KB Output is correct
3 Correct 97 ms 2736 KB Output is correct
4 Correct 206 ms 5608 KB Output is correct
5 Correct 180 ms 5168 KB Output is correct
6 Correct 139 ms 4436 KB Output is correct
7 Correct 221 ms 5576 KB Output is correct
8 Correct 174 ms 4852 KB Output is correct
9 Correct 222 ms 5508 KB Output is correct
10 Correct 89 ms 3152 KB Output is correct
11 Runtime error 1229 ms 28244 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -