Submission #1163953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163953		Joshua_Andersson	Colors (BOI20_colors)	C++20	9 / 100	0 ms	444 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++;
	if (secret == -1) init();
	int ret;
	if (last == -1000) ret = 0;
	else
	{
		ret = abs(x - last) >= secret;
	}
	//cout << "ASK " << x << ",DIFF=" << abs(x - last) << " " << ret << "\n";
	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;
	//		}
	//	}
	//}

	auto solve = [&](int n)
	{

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

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

		vi nums;
		{
			int lo = 0;
			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 = 0;
		int hi = n;
		int ind = 0;
		set<int> seen;
		seen.insert(s);

		auto valid = [&](int g)
		{
			if (g<0||g>n) return false;
			if (seen.count(g)) return false;
			return true;
		};

		vi tryv = { 0, 1,-1,2,-2 };
		int direction = -1;
		while (lo + 1 < hi)
		{
			int mid = (lo + hi) / 2;
			//cout << (ind%2?"+":"-") << mid << "\n";
			int g;
			if (ind % 2) g = last + mid;
			else g = last - mid;
			/*if (direction==-1)
			{
				if (last - mid >= 1) g = last - mid;
				else direction = 1, g = last + mid;
			}
			else
			{
				if (last + mid <= 1) g = last + mid;
				else direction = -1, g = last - mid;
			}*/
			assert(valid(g));
			
			seen.insert(g);
			if (ask(g))
			{
				hi = mid;
			}
			else lo = mid;
			last = g;
			ind++;
		}
		cout << "= " << hi << endl;
		//assert(hi == secret);
	};

	cin >> n;
	solve(n);
	return 0;

	/*n = 67;
	secret = 44;
	solve(n);

	repp(i, 2, 1000)
	{
		repp(j, 1, i + 1)
		{
			n = i;
			secret = j;
			solve(n);
		}
	}*/

	//cin >> n >> secret;*/



	return 0;
}

Compilation message (stderr)

Colors.cpp: In lambda function:
Colors.cpp:219:9: warning: control reaches end of non-void function [-Wreturn-type]
  219 |         };
      |         ^

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