Submission #96319

#	Time	Username	Problem	Language	Result	Execution time	Memory
96319		Noam527	Hotter Colder (IOI10_hottercolder)	C++17	93 / 100	872 ms	13232 KiB

hottercolder

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;

const int debugmode = 0;
const int more1 = 0;
const int more2 = 0;
const int L = 25;

int dp[2 * L + 2][L + 1][L + 1][2 * L + 2] = {};
int to[2 * L + 2][L + 1][L + 1][2 * L + 2] = {};

int calc(int sz, int l, int r, int prev, int change = 0) {
	if (l >= r) return 1;
	sz = min(sz, 2 * r);
	prev = min(prev, 2 * r);
	if (dp[sz][l][r][prev] != 0) return dp[sz][l][r][prev];
	int &D = dp[sz][l][r][prev], &t = to[sz][l][r][prev];
	int mn = md, tmp1, tmp2;
	for (int i = 1; i <= 2 * r && i <= sz; i++)
		if (i != prev) {
			int mid1 = (prev + i - 1) / 2, mid2 = (prev + i) / 2 + 1;
			if ((l <= mid1 && mid1 < r) || (l < mid2 && mid2 <= r)) {
				tmp1 = calc(sz, l, mid1, i, 0);
				tmp2 = calc(sz, mid2, r, i, 0);
				if (mn >= max(tmp1, tmp2)) {
					mn = max(tmp1, tmp2);
					if (!change) t = i;
				}
			}
			else if (change == 0) {
				tmp1 = calc(sz, l, r, i, 1);
				if (mn >= tmp1) {
					mn = tmp1;
					if (!change) t = i;
				}
			}
		}
//	printf("(%d, %d, %d, %d, %d) = %d\n", sz, l, r, prev, change, 1 + mn);
	if (!change) D = 1 + mn;
	return 1 + mn;
}
int goes(int sz, int l, int r, int prev) {
	sz = min(sz, 2 * r);
	prev = min(prev, 2 * r);
	calc(sz, l, r, prev);
	return to[sz][l][r][prev];
}
bool can(int l, int r) {
	return r < L + 1;
}
void cut(int &l, int &r, int &prev, int &pos, int k) {
	if ((k == -1) == (pos < prev)) {
		l = max(l, (pos + prev) / 2 + 1);
	}
	else {
		r = min(r, (pos + prev - 1) / 2);
	}
}
//#include "grader.h"

int n;
bool rev;
int myans, myprev = -1, mycnt;
/*
int Guess(int G) {
	mycnt++;
	if (debugmode) {
		cout << "? " << G << '\n';
		int rtn;
		cin >> rtn;
		return rtn;
	}
	else {
		int rtn;
		if (myprev == -1) rtn = 0;
		else {
			if (abs(myans - G) == abs(myans - myprev)) rtn = 0;
			else if (abs(myans - G) < abs(myans - myprev)) rtn = 1;
			else rtn = -1;
		}
		myprev = G;
		return rtn;
	}
}
*/
int Guess(int G);
int ask(int x) {
	if (rev) x = n + 1 - x;
	return Guess(x);
}

int solve(int sz, int l, int r, int prev) {
	sz = min(sz, 2 * r);
	prev = min(prev, 2 * r);
	while (l < r) {
		if (more1) cout << "solve " << sz << " " << l << " " << r << " " << prev << '\n';
		int pos = goes(sz, l, r, prev);
		int k = ask(pos);
		if (k == 0) {
			if ((pos + prev) % 2 == 0 && l <= (pos + prev) / 2 && (pos + prev) / 2 <= r)
				return (pos + prev) / 2;
			else {
				prev = pos;
				continue;
			}
		}
		cut(l, r, prev, pos, k);
		prev = pos;
	}
	return l;
}

int HCr(int l, int r, int prev) {
	int pos;
	while (l < r) {
		if (more1) cout << "HCr" << l << " " << r << '\n';
		pos = l + r - prev;
		while (pos < 1) pos++;
		int k = ask(pos);
		if (k == 0) return (pos + prev) / 2;
		cut(l, r, prev, pos, k);
		prev = pos;
	}
	return l;
}

int HC(int l, int r, int prev) {
	if (more1) cout << "HC " << l << " " << r << '\n';
	if (can(l, r)) return solve(n, 1, r, prev);
	int pos = prev / 2;
	int k = ask(pos);
	if (k == 0) return (pos + prev) / 2;
	cut(l, r, prev, pos, k);
	if (l == 1) return HC(l, r, pos);
	return HCr(l, r, pos);
}

int HC(int N) {
	n = N;
	rev = false;
	if (can(1, N)) return solve(N, 1, N, md);

	int p1 = n / 2, p2 = (n + 3) / 2;
	ask(p1);
	int k = ask(p2);
	int l = 1, r = n;
	if (k == 0) return (p1 + p2) / 2;
	cut(l, r, p1, p2, k);
	if (l > 1) {
		rev = true;
		swap(l, r);
		l = n + 1 - l;
		r = n + 1 - r;
		p2 = n + 1 - p2;
	}
	if (more1) cout << "before " << l << " " << r << " " << rev << '\n';
	if (more2 && can(l, r)) {
		int rtn = solve(n, l, r, p2);
		if (rev) rtn = n + 1 - rtn;
		return rtn;
	}
	p1 = (r + 1) / 2;
	k = ask(p1);
	if (k == 0) {
		if (!rev) return (p2 + p1) / 2;
		return n + 1 - (p2 + p1) / 2;
	}
	cut(l, r, p2, p1, k);
	int rtn = -1;
	if (l == 1) rtn = HC(l, r, p1);
	else rtn = HCr(l, r, p1);
	if (rev) rtn = n + 1 - rtn;
	return rtn;
}

/*
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	if (debugmode) {
		while (1) {
			cout << "x: ";
			int x;
			cin >> x;
			int ans = HC(x);
			cout << "ans: " << ans << '\n';
		}
	}
	else {
		for (int x = 1; x <= 500; x++) {
			for (int i = 1; i <= x; i++) {
				mycnt = 0;
				myans = i;
				myprev = -1;
				int ans = HC(x);
				if (ans != myans) {
					cout << "WA on " << x << " " << i << '\n';
					cout << "myans = " << myans << " provided = " << ans << '\n';
					return 0;
				}
				if ((1LL << mycnt) > 3 * x) {
					cout << "not good enough on " << x << " " << i << '\n';
					cout << "did " << mycnt << '\n';
					return 0;
				}
			}
		}
	}
}
*/

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 18 / 25