Submission #1247959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247959		DeathIsAwe	The Big Prize (IOI17_prize)	C++20	90 / 100	23 ms	5740 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
using namespace std;
bool isloli[200000], visited[200000];
vector<int> resultvec[200000];
int lolinum = 1;
bool changeloli = false;


void find(int a, int n) {
	//cout << a << endl;
	if (resultvec[a].size() == 0) resultvec[a] = ask(a);
	if (resultvec[a][0] + resultvec[a][1] > lolinum) {
		lolinum = resultvec[a][0] + resultvec[a][1];
		changeloli = true;
	}
	isloli[a] = ((resultvec[a][0] + resultvec[a][1]) == lolinum);
}


int find_best(int n) {
	for (int i=0;i<n;i++) {
		visited[i] = false;
	}


	int left, right, middle, temp;
	for (int i=0;i<n;i++) {
		if (visited[i]) continue;
		find(i, n);
		if (resultvec[i][0] + resultvec[i][1] == 0) return i;
		if (isloli[i]) {
			left = i; right = n;
			while (right > left + 1) {
				middle = (right + left) / 2;
				temp = middle;
				while (temp > left) {
					find(temp, n);
					if (resultvec[temp][0] + resultvec[temp][1] == 0) return temp;
					if (changeloli) break;
					if (!isloli[temp]) temp -= 1;
					else break;
				}
				if (changeloli) break;
				if (temp == left) {
					break;
				} else {
					if (resultvec[temp][0] == resultvec[i][0]) {
						left = middle;
					} else {
						right = temp;
					}
				}
			}
			if (changeloli) {changeloli = false; continue;}
			for (int j=i;j<left+1;j++) {
				visited[j] = true;
			}
		} else {
			visited[i] = true;
		}
	}
	return -1;
}

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