Submission #638198

#	Time	Username	Problem	Language	Result	Execution time	Memory
638198		dozer	Colors (BOI20_colors)	C++14	0 / 100	1 ms	208 KiB

Colors

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define modulo 1000000007
#define N 100005
#define int long long

int mm(pii r)
{
	return (r.st + r.nd + 1) / 2;
}

int m(pii l)
{
	return (l.st + l.nd) / 2;
}

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

int32_t main()
{
	int n;
	cin>>n;
	int mid = (n + 1) / 2;
	pii l = {1, mid};
	pii r = {mid + 1, n};
	int res = ask(m(l));
	res = ask(mm(r));
	int ll = 0, rr = n;
	while(l.st <= l.nd && r.st <= r.nd)
	{
		if (res == 1)
		{
			ll = m(l), rr = mm(r);
			l = {m(l) + 1, l.nd};
		}
		else
			l = {l.st, m(l) - 1};

		if (l.st <= l.nd)
		{
			res = ask(m(l));

			if (res == 1)
			{
				ll = m(l), rr = mm(r);
				r = {r.st, mm(r) - 1};
			}
			else r = {mm(r) + 1, r.nd};
			res = ask(mm(r));
		}
	}

	cout<<"= "<<rr - ll<<endl;


	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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