Submission #868878

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

prize

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

using namespace std;

const int LOG = 18, TAKE = 500;

int find_best(int n) {
	int mx = 0, id;

	// last apperance of num and cnt
	map<int, int> last;

	for(id = 0; id < min(TAKE, n); id++){
		auto c = ask(id);
		int s = c[0] + c[1];
		last[s] = c[0];
		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];
			last[s] = c[0];
			if(s == 0){
				return id;
			}
			if(s == mx){
				break;
			}
		}
		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(last.count(s) && c[0] == last[s]){
				ok = 0;
				last[s] = c[0];
			}
		}

		// overjump all biggest
		for(int j = (ok ? jump_point - 1 : 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(last.count(s) && c[0] == last[s]){
				id += jump;
				last[s] = c[0];
			}
		}
		// go to the next which is not max
		id++;
	}
	assert(false);
}

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