oj.uz

Submission #201975

# Submission time Handle Problem Language Result Execution time Memory
201975 2020-02-12T23:29:01 Z Benq Hotter Colder (IOI10_hottercolder) C++14
92 / 100
 921 ms 8272 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; 
		ckmax(des,1); ckmin(des,N);
		if (tri(des)) return posi.f;
	}
}

int HC(int _N) {
	N = _N;
	guess.clear(), soFar.clear(); posi = {1,N};
	if (N == 1) return 1;
	if (N == 2) {
		tri(1); assert(tri(2));
		return posi.f;
	}
	int m = (1+N)/2; 
	tri(m-1); if (tri(m+1)) return posi.f;
	if (posi.s == m-1) {
		while (posi.f == 1) {
			int p = max(posi.s/4,1);
			if (soFar.bk <= 3) {
				assert(tri(1));
				return posi.f;
			}
			if (tri(p+2)) return posi.f;
			// if (N == 65) cerr << "WUT " << posi.f << " " << posi.s << " " << p << "\n";
			if (posi.f != 1) return binSearch();
			if (tri(p)) return posi.f;
			if (posi.f != 1) return binSearch();
			assert(posi.s == p);
		}
	} else {
		assert(posi.f == m+1);
		while (posi.s == N) {
			if (soFar.bk >= N-2) {
				assert(tri(N));
				return posi.f;
			}
			int p = min(N+1-(N+1-posi.f)/4,N);
			if (tri(p-2)) return posi.f;
			if (posi.s != N) return binSearch();
			if (tri(p)) return posi.f;
			if (posi.s != N) return binSearch();
			assert(posi.f == p);
		}
	}
}

Compilation message

hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:108:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1400 KB Output is correct

Subtask #4
17.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 921 ms 8272 KB Output is partially correct - alpha = 0.666666666667