Submission #291902

#	Time	Username	Problem	Language	Result	Execution time	Memory
291902		Berted	Colors (BOI20_colors)	C++14	100 / 100	2 ms	416 KiB

Colors

#include <iostream>
#include <set>
#include <assert.h>
#define ll long long
using namespace std;

ll n; 

inline bool ask(ll x)
{
	bool ret;
	assert(1 <= x && x <= n);
	cout << "? " << x << endl;
	cin >> ret;
	return ret;
}

int main()
{
	int t = 1;
	while (t--)
	{
		cin >> n;
		ll s = 0, c = 0, L = 1, R = n - 1;
		for (int i = 0; L <= R; i++)
		{
			ll M = (R - L + 1 > 2) ? (L + R >> 1) : R;
			if (i & 1) {c -= M;}
			else {c += M;}
			s = min(s, c);
			L = M + 1;
		}
		s = -s + 1;
		L = 1, R = n - 1; ll ans = n;
		if (n > 1) ask(s);
		for (int i = 0; L <= R; i++)
		{
			ll M = (R - L + 1 > 2) ? (L + R >> 1) : R;
			if (i & 1) s -= M;
			else s += M;
			if (ask(s)) {ans = M; R = M - 1;}
			else {L = M + 1;}
		}
		cout << "= " << ans << endl;
	}
	
	return 0;
}

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:27:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |    ll M = (R - L + 1 > 2) ? (L + R >> 1) : R;
      |                              ~~^~~
Colors.cpp:38:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |    ll M = (R - L + 1 > 2) ? (L + R >> 1) : R;
      |                              ~~^~~

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