Submission #431316

#	Time	Username	Problem	Language	Result	Execution time	Memory
431316		Mazaalai	The Big Prize (IOI17_prize)	C++14	20 / 100	97 ms	872 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 = -1;
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 = 5, st = 0, end = n - 1, miniCnt = 0;
	PII A, B;
	for (int i = 0; i < m && !found; i++) {
		int j = i;
		PII cur = askPos(j);
		int curSum = sum(cur);
		if (curSum > miniCnt) miniCnt = curSum;
		if (curSum == miniCnt) 
			st = j;
	}
	for (int i = 0; i < m && !found; i++) {
		int j = n - 1 - i;
		PII cur = askPos(j);
		int curSum = sum(cur);
		if (curSum > miniCnt) miniCnt = curSum;
		if (curSum == miniCnt) 
			end = j;
	}
	// cout << miniCnt << '\n';
	int jumped = 0, addPos = 0;
	map <int, int> jumpIdx;

	while(st < end && !found) {
		// cout << st << ' ' << n << '\n';
		A = askPos(st);
		B = askPos(end);
		int l = st, r = end, res = l;
		while(l <= r) {
			int mid = (l+r)/2;
			PII cur = askPos(mid);
			if (A == cur) {
				res = max(res, mid);
				l = mid+1;
			} else {
				r = mid-1;
			}
		}
		st = res+1;		
		bool x = 1;
		while(x && !found) {
			x = 0;
			PII cur = askPos(st);
			int curSum = sum(cur);
			if (curSum != miniCnt) {
				x = 1;
				st++;
			}
		}	
		if (miniCnt != 1) {
			l = st, r = end, res = end;
			while(l <= r) {
				int mid = (l+r)/2;
				PII cur = askPos(mid);
				if (B == cur) {
					res = min(res, mid);
					r = mid-1;
				} else {
					l = mid+1;
				}
			}
			end = res-1;
			x = 1;
			while(x && !found) {
				x = 0;
				PII cur = askPos(end);
				int curSum = sum(cur);
				if (curSum != miniCnt) {
					x = 1;
					end--;
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:48:6: warning: unused variable 'jumped' [-Wunused-variable]
   48 |  int jumped = 0, addPos = 0;
      |      ^~~~~~
prize.cpp:48:18: warning: unused variable 'addPos' [-Wunused-variable]
   48 |  int jumped = 0, addPos = 0;
      |                  ^~~~~~

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