Submission #1163915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163915		Joshua_Andersson	Colors (BOI20_colors)	C++20	0 / 100	0 ms	432 KiB

Colors

#include <bitset>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;

typedef long long ll;
#define int ll
const int inf = int(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < (high); i++)
#define repp(i, low, high) for (int i = (low); i < (high); i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

inline void fast() { cin.tie(0)->sync_with_stdio(0); }

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

int n;
int numguess = 0;

#if !_LOCAL
int ask(int x)
{
	cout << "? " << x << endl;
	int resp;
	cin >> resp;
	return resp;
}
#else
int secret = -1;
void init()
{
	mt19937 rng(time(0));
	secret = uniform_int_distribution<int>(1, n)(rng);
	cout << "SECRET=" << secret << "\n";
}
int last = -1000;
int ask(int x)
{
	numguess++;
	//cout << "ASK " << x << ",DIFF=" << abs(x - last) << "\n";
	if (secret == -1) init();
	int ret;
	if (last == -1000) ret = 0;
	else
	{
		ret = abs(x - last) >= secret;
	}
	last = x;
	return ret;
}
#endif

signed main()
{
	fast();

	/*vi nums;
	int lo = 1;
	int hi = 239578;
	while (lo+1<hi)
	{
		int mid = (lo + hi) / 2;
		nums.push_back(mid);
		lo = mid;
	}
	repe(v, nums) cout << v << "\n";
	int ans = 0;
	rep(i, sz(nums)) ans += (i % 2 ? 1 : -1) * nums[i];
	cout << ans << " " << abs(ans-hi/3);
	cout << "";
	return 0;*/

	//n = int(1e9);
	////cin >> n;

	//if (n<=64)
	//{
	//	rep(i, n / 2)
	//	{
	//		if (ask(i + 1) == 0 && i)
	//		{
	//			cout << "= " << abs(n-(i-1)-i+1)-1 << endl;
	//			return 0;
	//		}
	//		if (ask(n - i) == 0)
	//		{
	//			cout << "= " << abs(n - i - (i + 1)) + 1 << endl;
	//			return 0;
	//		}
	//	}
	//}

	cin >> n;

	if (n==2)
	{
		int a = ask(1);
		int b = ask(2);
		if (b==1)
		{
			cout << "= " << 1 << endl;
		}
		else cout << "= " << 2 << endl;
		return 0;
	}

	if (n <= 64)
	{
		rep(i, n / 2)
		{
			if (ask(i + 1) == 0 && i)
			{
				cout << "= " << abs(n - (i - 1) - i + 1) - 1 << endl;
				return 0;
			}
			if (ask(n - i) == 0)
			{
				cout << "= " << abs(n - i - (i + 1)) + 1 << endl;
				return 0;
			}
		}
	}

	vi nums;
	{
		int lo = 1;
		int hi = n;
		while (lo + 1 < hi)
		{
			int mid = (lo + hi) / 2;
			nums.push_back(mid);
			lo = mid;
		}
	}
	int ma = 0;
	int mi = n;
	int ans = 0;
	rep(i, sz(nums)) ans += (i % 2 ? 1 : -1) * nums[i], ma = max(ma, ans), mi = min(mi, ans);
	//cout << ans << " " << abs(ans - hi / 3);

	int par = ans > 0;
	int s = -mi + 1;

	ask(s);
	int last = s;
	int lo = 1;
	int hi = n;
	int ind = 0;
	set<int> seen;
	while (lo + 1 < hi)
	{
		int mid = (lo + hi) / 2;

		int g;
		if (ind % 2 == 0) g = last - mid;
		else g = last + mid;
		assert(g >= 1 && g <= n);
		assert(!seen.count(g));
		seen.insert(g);
		if (ask(g))
		{
			hi = mid;
		}
		else lo = mid;
		last = g;
		ind++;
	}
	cout << "= " << hi << endl;


	return 0;
}

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