Submission #1263054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263054		cpismylifeOwO	Colors (BOI20_colors)	C++20	100 / 100	0 ms	432 KiB

Colors

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

long long n, c;

void Inp()
{
    cin >> n;
#ifdef cpismylifeOwO
    cin >> c;
#endif // cpismylifeOwO
}

int quecnt;
long long cur;
set<long long> s;

bool Ask(long long k)
{
    cout << "? " << k << "\n";
    cout.flush();
#ifdef cpismylifeOwO
    if (s.find(k) != s.end())
    {
        cout << "Rewrite\n";
    }
    s.insert(k);
    long long pre = cur;
    cur = k;
    quecnt++;
    cout << (abs(pre - k) >= c) << "\n";
    cout.flush();
    return (abs(pre - k) >= c);
#else
    bool p;
    cin >> p;
    return p;
#endif // cpismylifeOwO
}

void Ans(long long k)
{
    cout << "= " << k << "\n";
    cout.flush();
#ifdef cpismylifeOwO
    cout << (k == c) << "\n";
    cout.flush();
#endif // cpismylifeOwO
}

void Exc()
{
    cur = quecnt = 0;
    long long curmi = 0, now = 0, lt = 1, rt = n - 1;
    bool neg = true;
    while (lt <= rt)
    {
        long long mid = (lt + rt) / 2;
        if (neg)
        {
            now += mid;
            neg = false;
        }
        else
        {
            now -= mid;
            neg = true;
        }
        curmi = min(curmi, now);
        lt = mid + 1;
    }
    curmi = 1 - curmi;
    Ask(curmi);
    neg = true;
    long long l = 1, r = n - 1, mid, res = n;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (neg)
        {
            curmi += mid;
            neg = false;
        }
        else
        {
            curmi -= mid;
            neg = true;
        }
        if (Ask(curmi))
        {
            res = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    Ans(res);
}

int main()
{
    //freopen("COLORS.INP", "r", stdin);
    //freopen("COLORS.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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