Submission #722638

#	Time	Username	Problem	Language	Result	Execution time	Memory
722638		gagik_2007	Colors (BOI20_colors)	C++17	22 / 100	2 ms	208 KiB

Colors

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 31;
ll n, m, k;
bool lst = false;

bool ask(ll& cur, ll len) {
	ll nor = 0;
	if (lst) {
		nor = cur - len;
	}
	else {
		nor = cur + len;
	}
	lst = !lst;
	cout << "? " << nor << endl;
	cur = nor;
	bool res;
	cin >> res;
	return res;
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	if (n <= 64) {
		ll cur = 1;
		cout << "? " << cur << endl;
		bool kekw;
		cin >> kekw;
		ll len = n - 1;
		while (len > 0) {
			if (!ask(cur, len)) {
				cout << "= " << len + 1 << endl;
				return 0;
			}
			len--;
		}
		cout << "= " << 1 << endl;
		return 0;
	}
	else if (n <= 125) {
		bool kekw;
		ll cur = n / 2;
		cout << "? " << cur << endl;
		cin >> kekw;
		cur = 1;
		cout << "? " << cur << endl;
		cin >> kekw;
		if (kekw) {
			ll len = n / 2 - 2;
			while (len > 0) {
				if (!ask(cur, len)) {
					cout << "= " << len + 1 << endl;
					return 0;
				}
				len--;
			}
			cout << "= " << 1 << endl;
			return 0;
		}
		else {
			ll len = n - 1;
			while (len >= n / 2) {
				if (!ask(cur, len)) {
					cout << "= " << len + 1 << endl;
					return 0;
				}
				len--;
			}
			cout << "= " << n / 2 << endl;
			return 0;
		}
	}
	ll l = 1, r = n;
	ll cur = (n + 3) / 4 + 1;
	cout << "? " << cur << endl;
	bool kekw;
	cin >> kekw;
	while (l < r) {
		ll mid = (l + r) / 2;
		if (ask(cur, mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	cout << "= " << l << endl;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

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