Submission #1137677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137677		lightentheshadow	Colors (BOI20_colors)	C++20	43 / 100	0 ms	408 KiB

Colors

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

int main() {
    long long n;
    cin >> n;

    if (n == 1 || n > 1000) {
        cout << "= " << n;
        return 0;
    }

    if (n <= 63) {
        cout << "? 1" << endl;
        int l = 2, r = n, res;
        cin >> res;

        for (int i = 2; i <= n; i++) {
            if (i % 2) cout << "? " << l++ << endl;
                else cout << "? " << r-- << endl;
            cin >> res;
            if (res == 0) {
                cout << "= " << n - i + 2;
                return 0;
            }
        }

        cout << "= " << 1;
        return 0;
    }

    int x = sqrt(n), y = 1, cnt = 0;
    for (int i = x / 2; i <= x; i++) {
        int num = i;
        while (num + x <= n) num += x;
        if (n - num >= i - 1 && (n - num) - (i - 1) <= 1) {
            y = i;
            break;
        }
    }

    int save[55];
    while (y <= n) {
        save[++cnt] = y;
        y += x;
    }

    int l = 1, r = cnt, curr = 0, border = n, prev = save[cnt];
    cout << "? " << save[cnt] << endl;
    int ngaos; cin >> ngaos;

    while (l < r) {
        if (!curr) cout << "? " << save[l] << endl;
            else cout << "? " << save[r] << endl;

        int res;
        cin >> res;
        if (res == 1) {
            if (!curr) {
                border = abs(prev - save[l]);
                prev = save[l]; r--;
            }
            else {
                border = abs(prev - save[r]);
                prev = save[r]; l++;
            }
        }
        else {
            int P = save[l], Q = save[r], turn = 1 - curr;
            while (Q - P + 1 < border) {
                if (turn) cout << "? " << ++Q << endl;
                    else cout << "? " << --P << endl;
                turn = 1 - turn;
                cin >> res;
                if (res == 1) {
                    cout << "= " << Q - P;
                    return 0;
                }
            }
            cout << "= " << border;
            return 0;
        }

        curr = 1 - curr;
    }

    int turn = 0, bim = save[l];
    for (int i = border - 1; i >= 1; i--) {
        if (!turn) bim += i;
            else bim -= i;
        turn = 1 - turn;
        cout << "? " << bim << endl;

        int res; cin >> res;
        if (!res) {
            cout << "= " << i + 1;
            return 0;
        }
    }

    cout << "= " << 1;

    return 0;
}

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