Submission #999759

#	Time	Username	Problem	Language	Result	Execution time	Memory
999759		Gray	Colors (BOI20_colors)	C++17	0 / 100	1 ms	344 KiB

Colors

#include <bits/stdc++.h>
#include <cassert>

#define ll long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll MOD = (ll)1e9+7;
const ll INF = 2e18;
vector<ll> fact(1001);
ll binpow(ll a, ll b){
	if (!b) return 1;
	ll res=binpow(a, b/2);
	res=res*res%MOD;
	if (b%2) res=res*a%MOD;
	return res;
}
ll inv(ll x){
	return binpow(x, MOD-2);
}
ll bin(ll n, ll k){
	return fact[n]*inv(fact[n-k]*fact[k]%MOD)%MOD;
}
void gen(){
	fact[0]=1;
	for (ll i=1; i<=1000; i++){
		fact[i]=fact[i-1]*i%MOD;
	}
}


void solve(){
	ll n; cin >> n;
	ll rem = n%2;
	n-=rem;
	map<ll, ll> usd;
	ll l=0, r=n;
	ll prev=-1;
	while (l+1<r){
		ll mid = (l+r)/2;
		mid-=!(mid%2);
		// cout << mid << endl;
		if (usd[mid]) mid+=2;
		assert(!usd[mid]);
		usd[mid]=1;
		ll f = n/2+mid/2+1, s = n/2-mid/2;

		cout << "? " << f << endl;
		ll x; cin >> x;
		if (prev>-1){
			if (x){
				r=min(r, abs(prev-f));
			}else{
				l=max(l, abs(prev-f));
			}
		}
		cout << "? " << s << endl;
		cin >> x;
		if (x){
			r=min(mid, r);
		}else{
			l=max(l, mid);
		}
		prev=s;
	}
	if (r==n and rem){
		cout << "? " << n+rem << endl;
		ll x; cin >> x;
		if (!x) r=n+1;
	}
	cout << r << ln;
} 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	ll t=1; 
	// cin >> t;
	while (t--) solve();
}

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