Submission #417119

#	Time	Username	Problem	Language	Result	Execution time	Memory
417119		aryan12	Colors (BOI20_colors)	C++17	67 / 100	2 ms	304 KiB

Colors

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, ans;
int last;
map<int, int> used;

int get(int p) {
    used[p] = 1;
    cout << "? " << p << endl;
    int res;
    cin >> res;
    if(last && res && abs(last - p) < ans) {
        ans = abs(last - p);
    }
    last = p;
    return res;
}


int f(int x) {
    int i = n - x;
    return 1 + i / 2;
}

void Solve() {
    cin >> n;
    ans = n;
    int l = 1, r = n / 2 - (n % 2 == 0);
    while(l <= r) {
        int mid = (l + r) / 2;
        int a = f(mid + mid), b = f(mid + mid) + mid + mid;
        get(a);
        if(get(b)) {
            ans = min(mid + mid + 1, ans);
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    used[last] = 0;
    for(int i = 1; i + ans - 1 <= n && ans % 2 == 0 && ans > 1; i++) {
        if(!used[i] && !used[i + ans - 1]) {
            used[last] = 1;
            int a = i, b = i + ans - 1;
            if(b == last) {
                swap(a, b);
            }
            if(a != last) {
                get(a);
            }
            get(b);
            break;
        }
    }
    cout << "= " << ans << endl;
}
//
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Solve();
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 0 / 33