Submission #1225480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225480		jerzyk	Colors (BOI20_colors)	C++20	0 / 100	0 ms	320 KiB

Colors

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
map<ll, ll> zl, zp;

void Dyn(ll x)
{
	if(zl.find(x) != zl.end())
		return;
	//cout << x << "\n";
	if(x == 2)
	{
		zl[x] = 1;
		zp[x] = 2;
		return;
	}
	if(x == 3)
	{	
		zl[x] = 2;
		zp[x] = 2;
		return;
	}
	Dyn((x + 1) / 2);
	zp[x] = zl[(x + 1) / 2] + (x) / 2;
	zl[x] = x - zp[x] + 1;
}

void Rek(ll d, ll n, ll a, ll b, ll p, ll k, ll od)
{
	ll nw;
	if(a < b)
		nw = (a + b) / 2;
	else
		nw = (a + b + 1) / 2;
	if(od == 0)
	{
		if(a < b)
			nw += (n) / 2;
		else
			nw -= (n) / 2;
	}else
	{
		n = abs(a - b) + 1;
		if(a > b)
		{
			a -= n - (abs(a - b) + 1);
			b -= n - (abs(a - b) + 1);
			nw -= n - (abs(a - b) + 1);
			d += n - (abs(a - b) + 1);
		}
	}
	cout << "? " << d + nw << "\n";
	cin >> od;
	if(od == 1)
		k = min(k, abs(a - nw));
	else
		p = max(p, abs(a - nw) + 1);
	if(k <= p)
	{
		cout << "= " << p << "\n";
		return;
	}
	Rek(d, n, nw, a, p, k, od);

}

void BS(ll n)
{
	int od;
	ll a, b, p, k;
	p = 1;
	k = n;
	Dyn(n);
	a = zp[n];
	b = a - ((n) / 2);	
	cout << "? " << a << "\n";
	cin >> od;
	cout << "? " << b << "\n";
	cin >> od;
	if(od == 1)
		k = abs(b - a);
	else
		p = abs(b - a) + 1;
	swap(a, b);
	Rek(0LL, n, a, b, p, k, od);
}

void Colors()
{
	int t, i;
	ll n;
	cin >> t;
	for(i = 1; i <= t; ++i)
	{
		cin >> n;
		BS(n);
	}
}

int main ()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	Colors();

	return 0;
}

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