Submission #236574

#	Time	Username	Problem	Language	Result	Execution time	Memory
236574		pit4h	The Big Prize (IOI17_prize)	C++14	0 / 100	11 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];
	vector<vector<int>> calced(l+1);
	int lo = 0, hi = l, m;
	while(lo <= hi) {
		m = (lo + hi)/2;
		if(p+(1<<m) >= n) hi = m-1;
		calced[m] = ask(p+(1<<m));
		if(calced[m][0] + calced[m][1] == total && calced[m][0]-pref==0) {
			lo = m+1;
		}
		else {
			l = m;
			hi = m-1;
		}
	}
	for(int i=l; i>=0; --i) {
		if(p+(1<<i)>=n) continue;	
		auto res = (calced[i].empty()?ask(p + (1<<i)):calced[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: 0 / 20
• Subtask 2: 0 / 80