Submission #1288957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288957		user736482	Colors (BOI20_colors)	C++20	100 / 100	11 ms	8232 KiB

Colors

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
ll fct[1000007];
ll fp(ll a,ll b){
    ll c=1;while(b){if(b&1)c=(c*a)%MOD;a=(a*a)%MOD;b/=2;}
    return c;
}

ll n,a=2,d,z=0;
ll t=1;
ll pp;
ll gtn(){
    cin>>a;
    return a;
}
bool query(ll x){
    cout<<"? "<<x<<endl;
    bool ns;
    cin>>ns;return ns;

}
void ns(ll x){
    cout<<"= "<<x<<"\n";
}
void solve(){
    n=gtn();
    ll ps=0;
    ll x=n;
    while(x!=1){
        //cout<<n-(x+1)/2<<" "<<x<<"  ";
        ps=(n-(x+1)/2)-ps;
        x=(x+1)/2;
    }
    ps=min(ps+1,n-ps);
    //cout<<ps<<"\n";
    query(ps);
    ll ak=0;
    x=n;
    ll y=1;
    while(x!=1){
        //cout<<x/2+ak<<"\n";
        ps+=y*(x/2+ak);
        y=-y;
        if(!query(ps)){
            ak+=(x/2);
            x-=x/2;
        }
        else{
            x/=2;
        }
    }
    ns(ak+1);
}
int main(){
    fct[0]=1;
    for(ll i=1;i<1000007;i++)fct[i]=(fct[i-1]*i)%MOD;
    
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}

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