Submission #62158

#	Time	Username	Problem	Language	Result	Execution time	Memory
62158		reality	Hotter Colder (IOI10_hottercolder)	C++17	87 / 100	2351 ms	9760 KiB

hottercolder

#include "grader.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int step = 0;
const int MX = 130;
const int C = 53;
int dp[MX][MX][MX];
int fr[MX][MX][MX];
int f(int a,int b,int c) {
	if (a >= b)
		return 0;
	if (dp[a][b][c] != 1e9)
		return dp[a][b][c];
	int &ans = dp[a][b][c];
	for (int k = a;k <= b;++k)
		if (k != c) {
			int l = min(k,c);
			int r = max(k,c);
			int m1 = (l + r - 1) / 2;
			int m2 = (l + r) / 2 + 1;
			if (ans > max(f(a,m1,k),f(m2,b,k)) + 1)
				ans = max(f(a,m1,k),f(m2,b,k)) + 1,fr[a][b][c] = k;
		}
	return ans;
}
int HC(int N) {
	if (N == 1)
		return 1;
	++step;
	if (step == 1) {
		for (int i = 1;i < C;++i)
			for (int j = 1;j < C;++j)
				for (int k = 1;k < C;++k)
					dp[i][j][k] = 1e9;
	}
	srand(N * step);
	int l = 1,r = N,was = 0;
	while (l < r) {
		int m = (l + r) / 2;
		if (m == was) {
			if (m + 1 <= r)
				++m;
			else
				--m;
		}
		if (!was) {
			Guess(m + 1);
			was = m + 1;
		}
		int cnt = Guess(m);
		if (!cnt)
			return ((m + was) / 2);
		int m1 = (m + was - 1) / 2;
		int m2 = (m + was) / 2 + 1;
		if (m > was)
			cnt *= -1;
		if (cnt == 1)
			r = m1;
		else
			l = m2;
		was = m;
	}
	return l;
}

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