oj.uz

Submission #864132

# Submission time Handle Problem Language Result Execution time Memory
864132 2023-10-22T07:12:54 Z Unforgettablepl Mađioničar (COI22_madionicar) C++17
13 / 100
 811 ms 596 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
ID: samikgo1
TASK: wormhole
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const int INF = 1e9;
const ll modulo = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define int ll
int n,q;

bool check(int l,int r){
    if(l<1 or r>n)return false;
    q++;
    assert(q<=200000);
    cout << "? " << l << ' ' << r << endl;
    int a;cin>>a;
    return a==1;
}

int bin_search(int l,int r){
    if(!check(l,r))return 0;
    for(int jump=32768;jump;jump/=2){
        if(check(l-jump,r+jump)){l-=jump;r+=jump;}
    }
    return r-l+1;
}

void solve(){
    cin>>n;
    int ans = 0;
    for(int i=1;i<=n;i++){
        ans = max(ans, bin_search(i-ans/2,i+1+ans/2));
    }
    ans = max(ans,1ll);
    for(int i=1;i<=n;i++){
        ans = max(ans, bin_search(i-ans/2-(ans%2),i+ans/2+(ans%2)));
    }
    cout << "! " << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    int t;
//    cin >> t;
//    while(t--)
//    for(int i=1;i<=1000;i++){
//        if(encode2(i)>110)cout << i << ' ';
//    }
//    cout << endl;
    solve();
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 344 KB Output is correct
2 Correct 57 ms 344 KB Output is correct
3 Correct 61 ms 344 KB Output is correct
4 Correct 59 ms 596 KB Output is correct
5 Correct 62 ms 344 KB Output is correct
6 Correct 60 ms 344 KB Output is correct
7 Correct 30 ms 344 KB Output is correct
8 Correct 111 ms 344 KB Output is correct
9 Correct 69 ms 344 KB Output is correct
10 Correct 53 ms 344 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 344 KB Output is correct
2 Correct 57 ms 344 KB Output is correct
3 Correct 61 ms 344 KB Output is correct
4 Correct 59 ms 596 KB Output is correct
5 Correct 62 ms 344 KB Output is correct
6 Correct 60 ms 344 KB Output is correct
7 Correct 30 ms 344 KB Output is correct
8 Correct 111 ms 344 KB Output is correct
9 Correct 69 ms 344 KB Output is correct
10 Correct 53 ms 344 KB Output is correct
11 Correct 574 ms 344 KB Output is correct
12 Correct 572 ms 344 KB Output is correct
13 Correct 561 ms 344 KB Output is correct
14 Correct 732 ms 344 KB Output is correct
15 Correct 556 ms 344 KB Output is correct
16 Runtime error 807 ms 448 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 344 KB Output is correct
2 Correct 621 ms 344 KB Output is correct
3 Correct 804 ms 344 KB Output is correct
4 Runtime error 792 ms 444 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 344 KB Output is correct
2 Correct 57 ms 344 KB Output is correct
3 Correct 61 ms 344 KB Output is correct
4 Correct 59 ms 596 KB Output is correct
5 Correct 62 ms 344 KB Output is correct
6 Correct 60 ms 344 KB Output is correct
7 Correct 30 ms 344 KB Output is correct
8 Correct 111 ms 344 KB Output is correct
9 Correct 69 ms 344 KB Output is correct
10 Correct 53 ms 344 KB Output is correct
11 Correct 574 ms 344 KB Output is correct
12 Correct 572 ms 344 KB Output is correct
13 Correct 561 ms 344 KB Output is correct
14 Correct 732 ms 344 KB Output is correct
15 Correct 556 ms 344 KB Output is correct
16 Runtime error 807 ms 448 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -