Submission #431152

#	Time	Username	Problem	Language	Result	Execution time	Memory
431152		Mazaalai	The Big Prize (IOI17_prize)	C++14	0 / 100	3040 ms	276 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair <int, int> PII;

map <int, PII> asked;
int ans;
bool found;
PII askPos(int n) {
	if (asked.count(n)) return asked[n];
	vector <int> res = ask(n);
	PII cur = {res[0], res[1]};
	if (cur.ff + cur.ss == 0) {
		ans = n;
		found = 1;
	}
	return asked[n] = cur;
}
int middle(PII&a, PII&b) {
	return abs(a.ff - b.ff);
}
int sum(PII&a) {
	return a.ff + a.ss;
}
int find_best(int n) {
	found = 0;
	int m = 200, st = 0, miniCnt = 0;
	PII last;
	for (int i = 0; i < m && !found; i++) {
		PII cur = askPos(i);
		int curSum = sum(cur);
		if (curSum > miniCnt) miniCnt = curSum;
		if (curSum == miniCnt) {
			last = cur;
			st = i;
		}
	}
	int jump = 16, jumped = 0, addPos = 0;
	map <int, int> jumpIdx;
	while(st < n && jump >= 0 && !found) {
		if (st + (1<<jump) >= n) {
			jump--;
			continue;
		}
		int asking = st + (1<<jump) + addPos;
		PII cur = askPos(asking);
		int curSum = sum(cur);
		int mid = middle(last, cur);
		if (miniCnt != curSum) {
			jumped++;
			if (jumpIdx.count(jumped) && jumpIdx[jumped] > asking) {
				st = jumpIdx[jumped]+1;
				addPos = 0;
				jumped = 0;
				jump = 16;
				continue;
			}
			addPos--;
			continue;
		} else {
			jumpIdx[mid] = asking;
		}
		if (mid == 0 && miniCnt == curSum) {
			st += (1<<jump);
			continue;
		}
	}
	return ans;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80