oj.uz

답안 #864129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864129 2023-10-22T07:04:01 Z Unforgettablepl Mađioničar (COI22_madionicar) C++17
13 / 100
 1004 ms 436 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;

bool check(int l,int r){
    if(l<1 or r>n)return false;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 344 KB Output is correct
2 Correct 61 ms 344 KB Output is correct
3 Correct 61 ms 344 KB Output is correct
4 Correct 71 ms 344 KB Output is correct
5 Correct 73 ms 344 KB Output is correct
6 Correct 69 ms 344 KB Output is correct
7 Correct 32 ms 344 KB Output is correct
8 Correct 116 ms 344 KB Output is correct
9 Correct 74 ms 344 KB Output is correct
10 Correct 63 ms 344 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 344 KB Output is correct
2 Correct 61 ms 344 KB Output is correct
3 Correct 61 ms 344 KB Output is correct
4 Correct 71 ms 344 KB Output is correct
5 Correct 73 ms 344 KB Output is correct
6 Correct 69 ms 344 KB Output is correct
7 Correct 32 ms 344 KB Output is correct
8 Correct 116 ms 344 KB Output is correct
9 Correct 74 ms 344 KB Output is correct
10 Correct 63 ms 344 KB Output is correct
11 Correct 598 ms 344 KB Output is correct
12 Correct 629 ms 344 KB Output is correct
13 Correct 646 ms 344 KB Output is correct
14 Correct 784 ms 344 KB Output is correct
15 Correct 617 ms 344 KB Output is correct
16 Runtime error 1004 ms 436 KB Execution killed with signal 13
17 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 991 ms 344 KB Output is correct
2 Correct 828 ms 344 KB Output is correct
3 Correct 969 ms 344 KB Output is correct
4 Runtime error 1002 ms 432 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 344 KB Output is correct
2 Correct 61 ms 344 KB Output is correct
3 Correct 61 ms 344 KB Output is correct
4 Correct 71 ms 344 KB Output is correct
5 Correct 73 ms 344 KB Output is correct
6 Correct 69 ms 344 KB Output is correct
7 Correct 32 ms 344 KB Output is correct
8 Correct 116 ms 344 KB Output is correct
9 Correct 74 ms 344 KB Output is correct
10 Correct 63 ms 344 KB Output is correct
11 Correct 598 ms 344 KB Output is correct
12 Correct 629 ms 344 KB Output is correct
13 Correct 646 ms 344 KB Output is correct
14 Correct 784 ms 344 KB Output is correct
15 Correct 617 ms 344 KB Output is correct
16 Runtime error 1004 ms 436 KB Execution killed with signal 13
17 Halted 0 ms 0 KB -