Submission #804585

#	Time	Username	Problem	Language	Result	Execution time	Memory
804585		rnl42	Colors (BOI20_colors)	C++14	0 / 100	1 ms	336 KiB

Colors

    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
     
    int N;
    unordered_set<int> used;
     
    inline int getvalid(int N) {
        int mincur = 0, maxcur = 0;
        int cur = 0;
        int mini = 1, maxi = N;
        bool parity = false;
        while (mini <= maxi) {
            int mid = (mini+maxi)>>1;
            int next;
            if (!parity) {
                next = cur+mid;
            } else {
                next = cur-mid;
            }
            mini = mid+1;
            cur = next;
            parity ^= 1;
            mincur = min(mincur, cur);
            maxcur = max(maxcur, cur);
        }
        //assert(maxcur-mincur <= N-1);
        return -mincur;
    }
     
    inline bool query(int x) {
        assert(!used.count(x));
        cout << "? " << x+1 << '\n' << flush;
        assert(x >= 0 && x < N);
        used.insert(x);
        bool ret;
        cin >> ret;
        return ret;
    }
     
    signed main() {
        //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        cin >> N;
        int cur = getvalid(N);
        int mini = 1, maxi = N;
        query(cur);
        //bool parity = false;
        while (mini < maxi) {
            int mid = (mini+maxi)>>1;
            int next;
            if (cur+mid < N && !used.count(cur+mid)) {
                next = cur+mid;
            } else if (cur-mid >= 0 && !used.count(cur-mid)) {
                next = cur-mid;
            } else {
                int inter = 0;
                for (; used.count(inter) || used.count(inter+mid); inter++);
                query(inter);
                next = inter+mid;
            }
            if (query(next)) {
                maxi = mid;
            } else {
                mini = mid+1;
            }
            cur = next;
            //parity ^= 1;
        }
        cout << "= " << mini << '\n';
    }

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