Submission #592254

#	Time	Username	Problem	Language	Result	Execution time	Memory
592254		hail	Colors (BOI20_colors)	C++17	100 / 100	2 ms	336 KiB

Colors

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin>>n;

    ll l=0;
    ll u=n;

    vector<ll> max_i(0);

    ll k{};
    while(k<n-1)
    {
        k=(k+n)/2;
        max_i.push_back(k);
    }

    k= -1;
    ll c_prev{n};
    for(auto i=max_i.rbegin(); i!=max_i.rend(); i++)
    {
        c_prev += k*(*i);
        k*=-1;
    }
    if(c_prev>n/2) c_prev = 1 + n-c_prev;

    cout<<"? "<<c_prev<<endl;
    cin>>k;

    ll c_new; 

    k=1;

    ll inp;

    while(u-l>1)
    {
        c_new = c_prev+(k*((u+l)/2));
        k*=-1;
        cout<<"? "<<c_new<<endl;
        cin>>inp;
        if(inp) u=abs(c_new-c_prev);
        else l=abs(c_new-c_prev);
        c_prev=c_new;
    }

    cout<<"= "<<u<<endl;

    return 0;

    
}

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