Submission #1147692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147692		gyg	The Big Prize (IOI17_prize)	C++20	90 / 100	236 ms	2620 KiB

prize

// ZERO INDEXING

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second

int n;

map<int, pii> rsp;
pii qry(int i) {
	if (rsp.count(i)) return rsp[i];
	vec<sig> ans = ask(i);
	rsp[i] = {ans[0], ans[1]};
	return rsp[i];
}

int gd;
void gd_cmp() {
	for (int i = 0; i < min(500ll, n); i++)
		gd = max(gd, qry(i).fir + qry(i).sec);
}

vec<int> lst;
int cnt(int x) {
	int ans = 0;
	for (int y : lst) ans += (y <= x);
	return ans;
}
int srch(vec<int>& rm) {
	int lw = 0, hg = rm.size() - 1;
	while (lw < hg) {
		int md = (lw + hg) / 2;
		if (qry(rm[md]).fir + qry(rm[md]).sec != gd) return md;
		if (qry(rm[md]).fir - cnt(rm[md])) hg = md - 1;
		else lw = md + 1;
	}
	return lw;
}

void lst_cmp() {
	vec<int> rm;
	for (int i = 0; i < n; i++) rm.push_back(i);
	for (int x = 0; x < gd; x++) {
		int i = srch(rm);
		lst.push_back(rm[i]);
		rm.erase(rm.begin() + i);
	}
}

int ans_cmp() {
	for (int i : lst) 
		if (qry(i).fir + qry(i).sec == 0) return i;
	assert(false); return -1;
}

sig find_best(sig _n) {
	n = _n;

	gd_cmp();
	lst_cmp();
	int ans = ans_cmp();

	return ans;
}

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