oj.uz

Submission #850230

# Submission time Handle Problem Language Result Execution time Memory
850230 2023-09-16T07:41:38 Z 1075508020060209tc Mađioničar (COI22_madionicar) C++14
13 / 100
 1185 ms 28476 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 154 ms 4348 KB Output is correct
2 Correct 86 ms 3380 KB Output is correct
3 Correct 87 ms 3284 KB Output is correct
4 Correct 194 ms 5172 KB Output is correct
5 Correct 187 ms 5220 KB Output is correct
6 Correct 150 ms 4448 KB Output is correct
7 Correct 226 ms 5640 KB Output is correct
8 Correct 167 ms 4832 KB Output is correct
9 Correct 207 ms 5868 KB Output is correct
10 Correct 78 ms 3260 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4348 KB Output is correct
2 Correct 86 ms 3380 KB Output is correct
3 Correct 87 ms 3284 KB Output is correct
4 Correct 194 ms 5172 KB Output is correct
5 Correct 187 ms 5220 KB Output is correct
6 Correct 150 ms 4448 KB Output is correct
7 Correct 226 ms 5640 KB Output is correct
8 Correct 167 ms 4832 KB Output is correct
9 Correct 207 ms 5868 KB Output is correct
10 Correct 78 ms 3260 KB Output is correct
11 Runtime error 1185 ms 28280 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 1174 ms 28476 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 154 ms 4348 KB Output is correct
2 Correct 86 ms 3380 KB Output is correct
3 Correct 87 ms 3284 KB Output is correct
4 Correct 194 ms 5172 KB Output is correct
5 Correct 187 ms 5220 KB Output is correct
6 Correct 150 ms 4448 KB Output is correct
7 Correct 226 ms 5640 KB Output is correct
8 Correct 167 ms 4832 KB Output is correct
9 Correct 207 ms 5868 KB Output is correct
10 Correct 78 ms 3260 KB Output is correct
11 Runtime error 1185 ms 28280 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -