oj.uz

Submission #864134

# Submission time Handle Problem Language Result Execution time Memory
864134 2023-10-22T07:16:18 Z Unforgettablepl Mađioničar (COI22_madionicar) C++17
13 / 100
 976 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 = 1;
    for(int i=1;i<=n;i++){
        ans = max(ans, bin_search(i-ans/2,i+1+ans/2));
        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 57 ms 344 KB Output is correct
2 Correct 87 ms 344 KB Output is correct
3 Correct 73 ms 344 KB Output is correct
4 Correct 72 ms 344 KB Output is correct
5 Correct 68 ms 344 KB Output is correct
6 Correct 62 ms 344 KB Output is correct
7 Correct 45 ms 596 KB Output is correct
8 Correct 126 ms 344 KB Output is correct
9 Correct 82 ms 596 KB Output is correct
10 Correct 67 ms 384 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 344 KB Output is correct
2 Correct 87 ms 344 KB Output is correct
3 Correct 73 ms 344 KB Output is correct
4 Correct 72 ms 344 KB Output is correct
5 Correct 68 ms 344 KB Output is correct
6 Correct 62 ms 344 KB Output is correct
7 Correct 45 ms 596 KB Output is correct
8 Correct 126 ms 344 KB Output is correct
9 Correct 82 ms 596 KB Output is correct
10 Correct 67 ms 384 KB Output is correct
11 Correct 615 ms 344 KB Output is correct
12 Correct 641 ms 344 KB Output is correct
13 Correct 562 ms 344 KB Output is correct
14 Correct 781 ms 344 KB Output is correct
15 Correct 613 ms 344 KB Output is correct
16 Runtime error 941 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 976 ms 344 KB Output is correct
2 Correct 485 ms 344 KB Output is correct
3 Correct 946 ms 344 KB Output is correct
4 Runtime error 966 ms 432 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 57 ms 344 KB Output is correct
2 Correct 87 ms 344 KB Output is correct
3 Correct 73 ms 344 KB Output is correct
4 Correct 72 ms 344 KB Output is correct
5 Correct 68 ms 344 KB Output is correct
6 Correct 62 ms 344 KB Output is correct
7 Correct 45 ms 596 KB Output is correct
8 Correct 126 ms 344 KB Output is correct
9 Correct 82 ms 596 KB Output is correct
10 Correct 67 ms 384 KB Output is correct
11 Correct 615 ms 344 KB Output is correct
12 Correct 641 ms 344 KB Output is correct
13 Correct 562 ms 344 KB Output is correct
14 Correct 781 ms 344 KB Output is correct
15 Correct 613 ms 344 KB Output is correct
16 Runtime error 941 ms 448 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -