Submission #256731

#	Time	Username	Problem	Language	Result	Execution time	Memory
256731		spacewalker	The Big Prize (IOI17_prize)	C++14	20 / 100	127 ms	2048 KiB

prize

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

using namespace std;
constexpr int NMAX = 200000;
constexpr int NORMIE_MAX = 470;

int lessLeft[NMAX];
int lessRight[NMAX];

int totalHigher = -1;

pair<int, int> query(int i) {
	if (lessLeft[i] == -1) {
		vector<int> ans = ask(i);
		lessLeft[i] = ans[0];
		lessRight[i] = ans[1];
	}
	return {lessLeft[i], lessRight[i]};
}

int higherThan(int i) {
	auto [lx, ly] = query(i);
	return lx + ly;
}

void findAllValuables(int i, int j, int valBefore, int valAfter, vector<int> &ans) {
//	printf("FNV %d %d %d %d\n", i, j, valBefore, valAfter);
	if (i > j) return;
	else {
		int k = (i + j) / 2;
		int nonValBefore, nonValAfter;
		for (nonValAfter = k; nonValAfter <= j && higherThan(nonValAfter) != totalHigher; ++nonValAfter) {
			ans.push_back(nonValAfter);
		}
		for (nonValBefore = k; nonValBefore >= i && higherThan(nonValBefore) != totalHigher; --nonValBefore) {
			ans.push_back(nonValBefore);
		}
		if (lessLeft[nonValBefore] != valBefore) {
			findAllValuables(i, nonValBefore - 1, valBefore, lessRight[nonValBefore], ans);
		}
		if (lessRight[nonValAfter] != valAfter) {
			findAllValuables(nonValAfter + 1, j, lessLeft[nonValAfter], valAfter, ans);
		}
	}
}

int find_best(int n) {
	memset(lessLeft, -1, sizeof lessLeft);
	memset(lessRight, -1, sizeof lessRight);
	if (n <= NORMIE_MAX) {
		for (int i = 0; i < n - 1; ++i) {
			if (higherThan(i) == 0) return i;
		}
	}
	for (int i = 0; i < NORMIE_MAX; ++i) {
		totalHigher = max(totalHigher, higherThan(i));
	}
	int firstNonValuable = -1;
	for (int i = 0; i < n; ++i) {
		if (higherThan(i) == totalHigher) {
			firstNonValuable = i;
			break;
		}
	}
	vector<int> vToCheck;
	for (int i = 0; i < firstNonValuable; ++i) vToCheck.push_back(i);
	findAllValuables(firstNonValuable + 1, n - 1, query(firstNonValuable).first, 0, vToCheck);
	for (int i : vToCheck) {
		if (higherThan(i) == 0) return i;
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int higherThan(int)':
prize.cpp:23:7: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  auto [lx, ly] = query(i);
       ^

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