Submission #868189

#	Time	Username	Problem	Language	Result	Execution time	Memory
868189		n1k	The Big Prize (IOI17_prize)	C++17	20 / 100	38 ms	600 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int LOG = 18, TAKE = 100;

int find_best(int n) {
	int mn = 1e9, id, cnt = 0;
	for(id = 0; id < min(TAKE, n); id++){

		auto c = ask(id);
		int s = c[0] + c[1];
		if(s == 0){
			return id;
		}
		mn = min(mn, s);
	}
	while(id < n){
		// find next smallest num
		for(; id < n; id++){
			auto c = ask(id);
			int s = c[0] + c[1];
			if(s == 0){
				return id;
			}
			if(s == mn){
				cnt = c[0];
				break;
			}
		}
		// overjump all min
		for(int j = LOG; j >= 0; j--){
			int jump = 1<<j;
			if(id + jump >= n){
				continue;
			}
			auto c = ask(id + jump);
			int s = c[0] + c[1];
			if(s == 0){
				return  id + jump;
			}
			if(s == mn && c[0] == cnt){
				id += jump;
			}
		}
		// go to the next which is not min
		id++;
	}
	assert(false);
}
/*
5516
*/

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