Submission #258056

#TimeUsernameProblemLanguageResultExecution timeMemory
258056mieszko11bColors (BOI20_colors)C++14
0 / 100
1 ms256 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using uid = uniform_int_distribution<int>;

using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
using ordered_multiset = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = int(1e9) + 7;
const ll INF = ll(1e18) + 7;

#define X first
#define Y second

//~ mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

//~ int rand(int a, int b) {
	//~ return uid(a, b)(rng);
//~ }

void boost() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

ll n;
ll act;

bool ask(ll x) {
	if(x > n) {
		ask(act - (x - n));
		x = n;
	}
	if(x < 1) {
		ask(act + (1 - x));
		x = 1;
	}
	
	act = x;
	cout << "? " << x << endl;
	//~ fflush(stdout);
	int xx;
	cin >> xx;
	return (xx == 1);
}

void solve() {
	cin >> n;
	ll first = 1;
	ll m = 0, pocz = 1, mid;
	while(pocz < n) {
		mid = (pocz + n) / 2;
		if(m)
			first += (mid - pocz + 1);
		m ^= 1;
		pocz = mid + 1;
	}
	
	ask(first);
	int dir = 1;
	pocz = 1;
	ll kon = n;
	while(pocz < kon) {
		mid = (pocz + kon) / 2;
		if(ask(act + ll(dir) * mid))
			kon = mid;
		else
			pocz = mid + 1;
		dir = -dir;
	}
	
	cout << "= " << pocz << endl;
	//~ fflush(stdout);
}

int main() {
	//~ boost();
	int t = 1;
	//~ cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...