oj.uz

Submission #850239

# Submission time Handle Problem Language Result Execution time Memory
850239 2023-09-16T07:51:34 Z 1075508020060209tc Mađioničar (COI22_madionicar) C++14
38 / 100
 1296 ms 27924 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(0);
}
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;
int ans=0;
par[1]=1;
for(int i=2;i<=n+n+1-ans;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;
    }
    ans=max(ans,par[i]);
}
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 138 ms 3984 KB Output is correct
2 Correct 104 ms 2724 KB Output is correct
3 Correct 78 ms 2856 KB Output is correct
4 Correct 126 ms 3960 KB Output is correct
5 Correct 128 ms 3784 KB Output is correct
6 Correct 104 ms 3180 KB Output is correct
7 Correct 95 ms 3060 KB Output is correct
8 Correct 90 ms 2580 KB Output is correct
9 Correct 107 ms 4180 KB Output is correct
10 Correct 85 ms 2984 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 3984 KB Output is correct
2 Correct 104 ms 2724 KB Output is correct
3 Correct 78 ms 2856 KB Output is correct
4 Correct 126 ms 3960 KB Output is correct
5 Correct 128 ms 3784 KB Output is correct
6 Correct 104 ms 3180 KB Output is correct
7 Correct 95 ms 3060 KB Output is correct
8 Correct 90 ms 2580 KB Output is correct
9 Correct 107 ms 4180 KB Output is correct
10 Correct 85 ms 2984 KB Output is correct
11 Correct 1180 ms 27596 KB Output is correct
12 Correct 823 ms 20580 KB Output is correct
13 Correct 754 ms 20036 KB Output is correct
14 Correct 1128 ms 25976 KB Output is correct
15 Correct 840 ms 20920 KB Output is correct
16 Correct 812 ms 19552 KB Output is correct
17 Correct 883 ms 19404 KB Output is correct
18 Correct 1155 ms 25960 KB Output is correct
19 Correct 829 ms 19376 KB Output is correct
20 Correct 1014 ms 23704 KB Output is correct
21 Correct 924 ms 22340 KB Output is correct
22 Correct 848 ms 20212 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1296 ms 27924 KB too many queries
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 3984 KB Output is correct
2 Correct 104 ms 2724 KB Output is correct
3 Correct 78 ms 2856 KB Output is correct
4 Correct 126 ms 3960 KB Output is correct
5 Correct 128 ms 3784 KB Output is correct
6 Correct 104 ms 3180 KB Output is correct
7 Correct 95 ms 3060 KB Output is correct
8 Correct 90 ms 2580 KB Output is correct
9 Correct 107 ms 4180 KB Output is correct
10 Correct 85 ms 2984 KB Output is correct
11 Correct 1180 ms 27596 KB Output is correct
12 Correct 823 ms 20580 KB Output is correct
13 Correct 754 ms 20036 KB Output is correct
14 Correct 1128 ms 25976 KB Output is correct
15 Correct 840 ms 20920 KB Output is correct
16 Correct 812 ms 19552 KB Output is correct
17 Correct 883 ms 19404 KB Output is correct
18 Correct 1155 ms 25960 KB Output is correct
19 Correct 829 ms 19376 KB Output is correct
20 Correct 1014 ms 23704 KB Output is correct
21 Correct 924 ms 22340 KB Output is correct
22 Correct 848 ms 20212 KB Output is correct
23 Incorrect 1296 ms 27924 KB too many queries
24 Halted 0 ms 0 KB -