Submission #1163890

#TimeUsernameProblemLanguageResultExecution timeMemory
1163890Joshua_AnderssonColors (BOI20_colors)C++20
0 / 100
0 ms436 KiB
#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 = n;//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;
	ask(n/3);
	int last = n/3;
	int lo = 1;
	int hi = n;
	int ind = 0;
	while (lo+1<hi)
	{
		int mid = (lo + hi) / 2;
		
		int g;
		if (ind % 2 == 0) g = last + mid;
		else g = last-mid;
		if (ask(g))
		{
			hi = mid;
		}
		else lo = mid;
		last = g;
		ind++;
	}
	cout << "= " << hi << endl;
	cerr << "G= " << numguess;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...