Submission #1030727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030727		12345678	Colors (BOI20_colors)	C++17	67 / 100	1 ms	596 KiB

Colors

#include <bits/stdc++.h>

using namespace std;

const int nx=1005;

int n, tmp, l, r, t, lst, x, ql[nx], qr[nx], dp[nx], C, pv=-1;
set<int> used;

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

int main()
{
    cin>>n;
    //cin>>C;
    if (n<=64)
    {
        l=1, r=n+1;
        query(1);
        for (int i=1; i<n; i++)
        {
            if (i%2) r--, dp[r-l]=query(r);
            else l++, dp[r-l]=query(l);
        }
        for (int i=1; i<=n; i++) if (dp[i]) return cout<<"= "<<i, 0;
        return cout<<"= "<<n, 0;
    }
    l=1, r=n+1;
    for (int i=1; i<64; i++)
    {
        if (i%2) r--;
        else l++;
        ql[i]=l;
        qr[i]=r;
    }
    query(qr[63]);
    lst=ql[63];
    used.insert(ql[63]);
    used.insert(qr[63]);
    if (!query(ql[63]))
    {
        for (int i=62; i>=1; i--)
        {
            if (ql[i]==lst) lst=qr[i], t=query(qr[i]);
            else lst=ql[i], t=query(ql[i]);
            if (t) return cout<<"= "<<n-i, 0;
        }
        return cout<<"= "<<n, 0;
    }
    l=1, r=n-63;
    while (l<r)
    {
        int md=(l+r)/2;
        //cout<<"debug "<<l<<' '<<r<<' '<<md<<'\n';
        for (int i=1; i+md<=n; i++)
        {
            if (used.find(i)==used.end()&&used.find(i+md)==used.end())
            {
                query(i);
                t=query(i+md);
                used.insert(i);
                used.insert(i+md);
                break;
            }
        }
        if (t) r=md;
        else l=md+1;
    }
    cout<<"= "<<l, 0;
}

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:74:21: warning: right operand of comma operator has no effect [-Wunused-value]
   74 |     cout<<"= "<<l, 0;
      |                     ^

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