oj.uz

Submission #864130

# Submission time Handle Problem Language Result Execution time Memory
864130 2023-10-22T07:06:18 Z Unforgettablepl Mađioničar (COI22_madionicar) C++17
13 / 100
 986 ms 448 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=65536;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 84 ms 344 KB Output is correct
2 Correct 61 ms 344 KB Output is correct
3 Correct 53 ms 344 KB Output is correct
4 Correct 65 ms 344 KB Output is correct
5 Correct 58 ms 344 KB Output is correct
6 Correct 70 ms 344 KB Output is correct
7 Correct 32 ms 340 KB Output is correct
8 Correct 113 ms 344 KB Output is correct
9 Correct 61 ms 344 KB Output is correct
10 Correct 69 ms 344 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 344 KB Output is correct
2 Correct 61 ms 344 KB Output is correct
3 Correct 53 ms 344 KB Output is correct
4 Correct 65 ms 344 KB Output is correct
5 Correct 58 ms 344 KB Output is correct
6 Correct 70 ms 344 KB Output is correct
7 Correct 32 ms 340 KB Output is correct
8 Correct 113 ms 344 KB Output is correct
9 Correct 61 ms 344 KB Output is correct
10 Correct 69 ms 344 KB Output is correct
11 Correct 647 ms 344 KB Output is correct
12 Correct 628 ms 344 KB Output is correct
13 Correct 650 ms 344 KB Output is correct
14 Correct 773 ms 344 KB Output is correct
15 Correct 662 ms 344 KB Output is correct
16 Runtime error 974 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 984 ms 344 KB Output is correct
2 Correct 776 ms 344 KB Output is correct
3 Correct 978 ms 344 KB Output is correct
4 Runtime error 986 ms 428 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 84 ms 344 KB Output is correct
2 Correct 61 ms 344 KB Output is correct
3 Correct 53 ms 344 KB Output is correct
4 Correct 65 ms 344 KB Output is correct
5 Correct 58 ms 344 KB Output is correct
6 Correct 70 ms 344 KB Output is correct
7 Correct 32 ms 340 KB Output is correct
8 Correct 113 ms 344 KB Output is correct
9 Correct 61 ms 344 KB Output is correct
10 Correct 69 ms 344 KB Output is correct
11 Correct 647 ms 344 KB Output is correct
12 Correct 628 ms 344 KB Output is correct
13 Correct 650 ms 344 KB Output is correct
14 Correct 773 ms 344 KB Output is correct
15 Correct 662 ms 344 KB Output is correct
16 Runtime error 974 ms 448 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -