Submission #638213

#	Time	Username	Problem	Language	Result	Execution time	Memory
638213		dozer	Colors (BOI20_colors)	C++14	9 / 100	1 ms	336 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 t = 1;
	//cin>>t;
	while(t--)
	{
		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;
		int steps = 2;
		int vl = 1, vr = n;
		while(l.st <= l.nd && r.st <= r.nd && vl < vr)
		{
			if (res == 1)
			{
				ll = m(l), rr = mm(r);
				vr = mm(r) - m(l);
				l = {m(l) + 1, l.nd};
			}
			else
			{
				vl = mm(r) - m(l) + 1;
				l = {l.st, m(l) - 1};
			}

			//cout<<vl<<sp<<vr<<endl;
			//cout<<l.st<<sp<<l.nd<<endl;
			//cout<<r.st<<sp<<r.nd<<endl;

			if (l.st <= l.nd && vl < vr)
			{
				if (steps == 64) return 1;
				res = ask(m(l));
				steps++;
				if (res == 1)
				{
					ll = m(l), rr = mm(r);
					vr = min(vr, mm(r) - m(l));
					r = {r.st, mm(r) - 1};
				}
				else
				{ 
					vl = max(vl, mm(r) - m(l) + 1);
					r = {mm(r) + 1, r.nd};
				}

				if (r.st <= r.nd && vl < vr) 
				{
					if (steps == 64) return 1;
					res = ask(mm(r));
					steps++;
				}
			}
			//cout<<l.st<<sp<<l.nd<<endl;
			//cout<<r.st<<sp<<r.nd<<endl;
		}

		int ans = rr - ll;
		if (vl == vr) ans = vl;
		cout<<"= "<<ans<<endl;
	}

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

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