Submission #1276497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276497		BigBadBully	Colors (BOI20_colors)	C++20	67 / 100	1 ms	408 KiB

Colors

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int inf = 1e18;
const int maxv = 1e9;

pii intersect(pii a, pii b)
{
    if (a.ff > b.ff)
        swap(a, b);
    if (a.ss >= b.ss)
        return b;
    return {b.ff, a.ss};
}

int _now = 0;
int c;
int fin = 0;
/*
int grader(int x)
{
    bool g = (abs(_now-x)>=c);
    _now = x;
    fin++;
    return g;
}*/

int grader(int x)
{
    cout << "? " << x << endl;
    cin >> x;
    return x;
}


void solve()
{
    int n;
    cin >> n;
    if(n==2){

        grader(1);
        if(grader(2))
        {
            cout << "= 1" << endl;
        }
        else
            cout << "= 2" << endl;

        return;

    }
    //cin >> c;
    pii seg = {1, n};
    map<int, int> kor;
    auto relax = [&](pii x)
    {
        seg = intersect(seg, x);
    };
    int now = 0;
    int qs = 0;
    auto query = [&](int l, int r)
    {
        kor[l]=1,kor[r]=1;
        int a;
        a = grader(l);
        
        if (qs)
        {
            if (a)
                relax({1, abs(l-now)});
            else
                relax({abs(l-now) + 1, n});
        }
        now = l;
        a = grader(r);
        qs++;
        
        if (a)
            relax({1, abs(r - l)});
        else
            relax({abs(r - l) + 1, n});
        now = r;
    };

    while(seg.ss-seg.ff > 1)
    {
        int l = seg.ff,r = seg.ss;
        int mid = l+r>>1;
        if(((mid%2)^(n%2)) == 0)
        {
            int a = max(abs(mid-l),abs(r-mid+1));
            int b= max(abs(r-mid-1),abs(mid+2-l));
            if (a < b)
                mid--;
            else
                mid++;
        }
        query((n+1)/2-(mid+1)/2 +(n%2==0),(n+1)/2+(mid+1)/2);
    }
    if(seg.ss==seg.ff)
    {
        cout << "= " << seg.ff << endl;
    }
    else
    {
        if ((now-seg.ff > 0 && !kor[now-seg.ff]))
        {
            if (grader(now-seg.ff))
                cout << "= " << seg.ff << endl;
            else
                cout << "= " << seg.ss << endl;
            cerr << fin << endl;
            return;
        }
         if ((now+seg.ff <= n && !kor[now+seg.ff]))
        {
            if (grader(now+seg.ff))
                cout << "= " << seg.ff << endl;
            else
                cout << "= " << seg.ss << endl;
            cerr << fin << endl;
            return;
        }
        for (int i = 1; i+seg.ff <= n; i++)
            if (!kor[i] && !kor[i+seg.ff])
            {
                query(i,i+seg.ff);
                cout << "= " << seg.ff << endl;
                break;
            }
    }

    cerr << fin << endl;
    fin = 0;
    _now = 0;
}

signed main()
{
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    */int t = 1;
    //cin >> t;
    while(t--)
    solve();
    
}

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