Submission #236569

#	Time	Username	Problem	Language	Result	Execution time	Memory
236569		pit4h	The Big Prize (IOI17_prize)	C++14	90 / 100	78 ms	512 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+1;
int total;
int n;
vector<int> vec;
int get_next(int pos) {
	int l = log2(n-1 - pos);	
	int p = pos;
	auto Ask = ask(p+1);
	if(Ask[0] + Ask[1] != total) {
		return p+1;
	}
	int pref = Ask[0];
	int l1 = min(max(1, l-3), 9);
	auto check = ask(p+(1<<(l1)));
	if(check[0] + check[1] != total || check[0] - pref != 0) {
		l = l1;
	}
	if(l != l1) {
		l1 = min(max(1, l-2), 14);
		auto check = ask(p+(1<<(l1)));
		if(check[0] + check[1] != total || check[0] - pref != 0) {
			l = l1;
		}
	}
	for(int i=l; i>=0; --i) {
		if(p+(1<<i)>=n) continue;	
		auto res = ask(p + (1<<i));
		if(res[0] - pref==0 && res[0]+res[1]==total) {
			p += (1<<i);
		}
	}
	p++;
	return p;
}
int find_best(int N) {
	n = N;
	int pos = -1;
	for(int i=0; i<min(n, 500); ++i) {
		auto res = ask(i);
		if(i!=0 && res[0] + res[1] > total) {
			total = res[0] + res[1];
			pos = i-1;
		}
		if(res[0] + res[1]==0) return i;
		if(res[0] + res[1] < total) pos = i;
		if(total > 500) break;
	}
	while(true) {
		pos = get_next(pos);
		auto Ask = ask(pos);
		if(Ask[0] + Ask[1] == 0) return pos;
	}
	return 0;
}

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