oj.uz

Submission #948674

# Submission time Handle Problem Language Result Execution time Memory
948674 2024-03-18T10:29:12 Z dimashhh Colors (BOI20_colors) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5 + 5, MOD = 998244353;

int LST = -1;
int ask(int x,int y){
    cout << "? " << x << endl;
    int a;cin >> a;
    cout << "? " << y << endl;
    cin >> a;
    LST = y;
    return a;
}
int n;
bool vis[N];
bool check(int x){
    if(LST + x <= n && !vis[LST + x]){
        cout << "? " << LST + x << endl;
        int a;
        cin >> a;
        vis[LST + x] = 1;
        LST += x;
        return a;
    }
    x *= -1;
    if(LST + x >= 1&& !vis[LST + x]){
        cout << "? " << LST + x << endl;
        int a;
        cin >> a;
        vis[LST + x] = 1;
        LST += x;
        return a;
    }
    x *= -1;
    for(int i = n;i >= 1;i--){
        if(i + x <= n && !vis[i] && !vis[i + x]){
            vis[i] = vis[i + x] = 1;
            return ask(i,i+x);
        }
    }
    return false;
}
void test() {
    cin >> n;
    int l = 0,r = n;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(check(mid)){
            r = mid;
        }else
            l = mid;
    }
    cout << "= " << r << endl;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (3 queries)
2 Correct 0 ms 344 KB OK (9 queries)
3 Correct 0 ms 344 KB OK (3 queries)
4 Correct 0 ms 344 KB OK (4 queries)
5 Correct 1 ms 344 KB OK (5 queries)
6 Incorrect 0 ms 344 KB Wrong guess
7 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (3 queries)
2 Correct 0 ms 344 KB OK (9 queries)
3 Correct 0 ms 344 KB OK (3 queries)
4 Correct 0 ms 344 KB OK (4 queries)
5 Correct 1 ms 344 KB OK (5 queries)
6 Incorrect 0 ms 344 KB Wrong guess
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (3 queries)
2 Correct 0 ms 344 KB OK (9 queries)
3 Correct 0 ms 344 KB OK (3 queries)
4 Correct 0 ms 344 KB OK (4 queries)
5 Correct 1 ms 344 KB OK (5 queries)
6 Incorrect 0 ms 344 KB Wrong guess
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (3 queries)
2 Correct 0 ms 344 KB OK (9 queries)
3 Correct 0 ms 344 KB OK (3 queries)
4 Correct 0 ms 344 KB OK (4 queries)
5 Correct 1 ms 344 KB OK (5 queries)
6 Incorrect 0 ms 344 KB Wrong guess
7 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (3 queries)
2 Correct 0 ms 344 KB OK (9 queries)
3 Correct 0 ms 344 KB OK (3 queries)
4 Correct 0 ms 344 KB OK (4 queries)
5 Correct 1 ms 344 KB OK (5 queries)
6 Incorrect 0 ms 344 KB Wrong guess
7 Halted 0 ms 0 KB -