Submission #676392

#	Time	Username	Problem	Language	Result	Execution time	Memory
676392		dooompy	Colors (BOI20_colors)	C++17	100 / 100	4 ms	336 KiB

Colors

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

int res(ll loc) {
    cout << "? " << loc << endl;

    int r; cin >> r;
    return r;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    ll n; cin >> n;

    ll l = 1, r = n - 1, ans = n;

    vector<ll> dist;

    while (l <= r) {
        ll m = (l + r) / 2;

        dist.push_back(m);
        l = m  +1;
    }

    ll loc = 1;
    ll flag = 1;

    for (int i = dist.size() - 1; ~i; i--) {
        loc += flag * dist[i];
        flag = -flag;
    }

    res(loc);
    l = 1, r= n  -1;
    while (l <= r) {
        ll m = (l + r) / 2;

        loc += flag * m;
        flag = -flag;

        if (res(loc) == 1) {
            ans = m;
            r = m - 1;
        } else l = m + 1;
    }

    cout << "= " << ans << endl;
}

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