Submission #1184977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184977		hamzabc	The Big Prize (IOI17_prize)	C++20	100 / 100	19 ms	12296 KiB

prize

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


using namespace std;


vector<int> glst;


void init(int l, int r){
	if (l > r)
		return;
	int m = (l + r) >> 1;
	glst.push_back(m);
	init(l, m - 1);
	init(m + 1, r);
}


int find_best(int n) {
	init(0, n - 1);
	vector<bool> blocked(n, false);
	map<long long, int> zip;
	vector<vector<pair<int, int>>> lst(6, vector<pair<int, int>>(n, { -1, -1 }));
	int k = 1;
	for (int i : glst){
		if (blocked[i])
			continue;
		vector<int> ret = ask(i);
		if (ret[0] + ret[1] == 0)
			return i;
		if (!zip[ret[0] + ret[1]]){
			zip[ret[0] + ret[1]] = k;
			k++;
		}
		if (lst[zip[ret[0] + ret[1]] - 1][ret[0]].first == -1){
			lst[zip[ret[0] + ret[1]] - 1][ret[0]].first = lst[zip[ret[0] + ret[1]] - 1][ret[0]].second = i;
		}else{
			if (i < lst[zip[ret[0] + ret[1]] - 1][ret[0]].first){
				for (int o = i; o < lst[zip[ret[0] + ret[1]] - 1][ret[0]].first; o++)
					blocked[o] = true;
				lst[zip[ret[0] + ret[1]] - 1][ret[0]].first = i;
			}else{
				for (int o = lst[zip[ret[0] + ret[1]] - 1][ret[0]].second; o < i; o++)
					blocked[o] = true;
				lst[zip[ret[0] + ret[1]] - 1][ret[0]].second = i;
			}
		}
	}
	return 0;
}

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