Submission #1030452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030452		12345678	Colors (BOI20_colors)	C++17	0 / 100	1 ms	380 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], used[nx];

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

int main()
{
    cin>>n;
    if (n==1) return cout<<"= "<<1, 0;
    for (int i=1; i<n; i++) ql[i]=1+(n-i)/2, qr[i]=n-((n-i)-1)/2; //cout<<"debug "<<i<<' '<<ql[i]<<' '<<qr[i]<<'\n';
    l=r=n;
    for (int i=63; ; i--)
    {
        l=max(1, r-i);
        if (l==r) return cout<<"= "<<l, 0;
        if (ql[l]==ql[l+1]) lst=ql[l], query(qr[l]), t=query(ql[l]), used[qr[l]]=used[ql[l]]=1;
        else lst=qr[l], query(ql[l]), t=query(qr[l]), used[qr[l]]=used[ql[l]]=1;
        if (t)
        {
            r=l;
            continue;
        }
        else
        {
            for (int j=l+1; j<r; j++)
            {
                if ((lst!=ql[j]&&used[ql[j]])||(lst!=qr[j]&&used[qr[j]]))
                {
                    l=j;
                    break;
                }
                if (lst==ql[j])
                {
                    lst=qr[j];
                    t=query(qr[j]);
                }
                else
                {
                    lst=ql[j];
                    t=query(ql[j]);
                }
                if (t) return cout<<"= "<<j, 0;
                if (j==r-1) return cout<<"= "<<r, 0;
            }
            
            if (l==r) return cout<<"= "<<l, 0;
            for (int j=1; j+l<=n; j++)
            {
                if (!used[j]&&!used[j+l])
                {
                    query(j);
                    t=query(j+l);
                    if (t) return cout<<"= "<<l<<'\n', 0;
                    else return cout<<"= "<<r<<'\n', 0;
                }
            }
        }
    }
}

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