oj.uz

Submission #201977

# Submission time Handle Problem Language Result Execution time Memory
201977 2020-02-13T00:15:43 Z Benq Hotter Colder (IOI10_hottercolder) C++14
100 / 100
 1672 ms 8192 KB 
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi; 
typedef vector<pi> vpi;

#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define bk back()
#define pb push_back

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7;
const ld PI = acos((ld)-1);

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }

vi soFar, guess;
pi posi;
int N;

bool tri(int x) {
	guess.pb(Guess(x));
	if (guess.bk == 0) {
		if (sz(soFar) && soFar.bk != x) 
			posi.f = posi.s = (soFar.bk+x)/2;
	} else {
		if (guess.bk == -1) {
			if (x < soFar.bk) {
				ckmax(posi.f,(soFar.bk+x)/2+1);
			} else {
				ckmin(posi.s,(soFar.bk+x-1)/2);
			}
		} else {
			if (x < soFar.bk) {
				ckmin(posi.s,(soFar.bk+x-1)/2);
			} else {
				ckmax(posi.f,(soFar.bk+x)/2+1);
			}
		}
	}
	soFar.pb(x); assert(posi.f <= posi.s);
	return posi.f == posi.s;
}

int binSearch() {
	while (1) {
		int des = posi.f+posi.s-soFar.bk; 
		// if (N == 5) ps("??",posi,soFar.bk,des);
		ckmax(des,1); ckmin(des,N);
		if (tri(des)) return posi.f;
	}
}

int HC(int _N) {
	// cout << "HA " << _N << endl;
	N = _N;
	guess.clear(), soFar.clear(); posi = {1,N};
	if (N == 1) return 1;
	int m = N/2+1;
	int a = m-1, b = m;
	tri(a); if (tri(b)) return posi.f;
	if (posi.f == 1) {
		while (1) {
			if (soFar.bk <= 3) {
				assert(tri(1));
				return posi.f;
			}
			if (soFar.bk <= 7) {
				tri(1);
				return binSearch();
			}
			vi one = {3}, two = {7};
			for (int i = 3;;++i) {
				if (i&1) {
					one.pb(one.bk+(1<<i));
					if (one.bk >= soFar.bk) {
						int p = one[sz(one)-2];
						if (tri(p+2)) return posi.f;
						if (posi.f != 1) return binSearch();
						if (tri(p)) return posi.f;
						if (posi.f != 1) return binSearch();
						break;
					}
				} else {
					two.pb(two.bk+(1<<i));
					if (two.bk >= soFar.bk) {
						int p = two[sz(two)-2];
						if (tri(p+2)) return posi.f;
						if (posi.f != 1) return binSearch();
						if (tri(p)) return posi.f;
						if (posi.f != 1) return binSearch();
						break;
					}
				}
			}
		}
	} else {
		while (1) {
			if (soFar.bk >= N+1-3) {
				assert(tri(N));
				return posi.f;
			}
			if (soFar.bk >= N+1-7) {
				tri(N);
				return binSearch();
			}
			vi one = {3}, two = {7};
			for (int i = 3;;++i) {
				if (i&1) {
					one.pb(one.bk+(1<<i));
					if (N+1-one.bk <= soFar.bk) {
						int p = one[sz(one)-2];
						if (tri((N+1)-(p+2))) return posi.f;
						if (posi.s != N) return binSearch();
						if (tri(N+1-p)) return posi.f;
						if (posi.s != N) return binSearch();
						break;
					}
				} else {
					two.pb(two.bk+(1<<i));
					if (N+1-two.bk <= soFar.bk) {
						int p = two[sz(two)-2];
						if (tri((N+1)-(p+2))) return posi.f;
						if (posi.s != N) return binSearch();
						if (tri((N+1)-p)) return posi.f;
						if (posi.s != N) return binSearch();
						break;
					}
				}
			}
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1272 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1272 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1672 ms 8192 KB Output is partially correct - alpha = 1.000000000000