Submission #868874

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

prize

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

using namespace std;

const int LOG = 18, TAKE = 500;

int find_best(int n) {
	int have = 2e5 - TAKE;
	int mx = 0, 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;
		}
		mx = max(mx, s);
	}
	while(id < n){
		// find next biggest num
		for(; id < n; id++){
			auto c = ask(id);
			int s = c[0] + c[1];
			if(s == 0){
				return id;
			}
			if(s == mx){
				cnt = c[0];
				break;
			}
		}
		// test 7 if not jump all
		int jump_point = 9;
		bool ok = 1;
		int jump = 1<<jump_point;
		if(id + jump < n){
			auto c = ask(id + jump);
			int s = c[0] + c[1];
			if(s == 0){
				return  id + jump;
			}
			if(s == mx && c[0] == cnt){
				ok = 0;
			}
		}

		// overjump all biggest
		for(int j = (ok ? jump_point - 1 : ceil(log2(have))); 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 == mx && c[0] == cnt){
				id += jump;
				have -= jump;
			}
		}
		// go to the next which is not max
		id++;
	}
	assert(false);
}
/*
what is the max call to jump LOG
max number of jumps > 2^10
2e5 - 800 <= cnt <= 2e5 - sqrt(2e5)
199552 <= cnt 
*/

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