Submission #1101682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101682		NoMercy	Colors (BOI20_colors)	C++14	100 / 100	2 ms	592 KiB

Colors

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int ask (ll x) {
	cout << "? " << x << endl;
	int res;
	cin >> res;
	return res;
}

int32_t main () {

	// ios_base::sync_with_stdio(0); 
	// cin.tie(0); 
	// cout.tie(0); 

	ll N;
	cin >> N;
	ll ind = 1, lo = 0, hi = N;
	vector<ll> all;
	map<ll, bool> used;
    while (lo + 1 < hi) {
        ll mid = (lo + hi) >> 1;
		all.push_back(mid);
        lo = mid;
    }
	reverse(all.begin(), all.end());
	for (int i = 0;i < all.size();i ++) {
		ind = ind + (ind + all[i] <= N ? all[i] : -all[i]);
	}
	used[ind] = 1;
    ask (ind);
	lo = 0;
	hi = N;
	while (lo + 1 < hi) {
		ll mid = (lo + hi) >> 1;
		// cout << lo << " " << mid << " " << hi << " " << ind << "\n";
		if (ind - mid >= 1 && used[ind - mid] == false) {
			if (ask (ind - mid) == 1) {
				hi = mid;
			} else {
				lo = mid;
			}
			ind = ind - mid;
		} else if (ind + mid <= N && used[ind + mid] == false) {
			if (ask (ind + mid) == 1) {
				hi = mid;
			} else {
				lo = mid;
			}
			ind = ind + mid;
		} else {
			if (ind - 1 >= N - ind) {
				if (ask(1) == 1) {
					hi = ind;
				} else {
					lo = ind;
				}
				ind = 1;
			} else {
				if (ask(N) == 1) {
					hi = N - ind;
				} else {
					lo = N - ind;
				}
				ind = N;
			}
		}
		used[ind] = true;
	}
	cout << "= " << hi << endl;
}

Compilation message (stderr)

Colors.cpp: In function 'int32_t main()':
Colors.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = 0;i < all.size();i ++) {
      |                 ~~^~~~~~~~~~~~

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