Submission #948674

#	Time	Username	Problem	Language	Result	Execution time	Memory
948674		dimashhh	Colors (BOI20_colors)	C++17	0 / 100	1 ms	344 KiB

Colors

#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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 33