Submission #862134

#	Time	Username	Problem	Language	Result	Execution time	Memory
862134		maks007	popa (BOI18_popa)	C++14	37 / 100	157 ms	596 KiB

popa

#include "bits/stdc++.h"
#include "popa.h"
//#include "grader.cpp"

using namespace std;

vector <int> Left, Right;
int root;

void F(int l, int r, int whom = -1, int flag = 0) {
	if(l > r) return;
	if(l == r) {
		if(flag == -1) Left[whom] = l;
		else Right[whom] = l;
		return;
	}
	for(int i = l; i <= r; i ++) {
		if(query(i, i, l, r)) {
			if(whom == -1) root = i;
			else {
				if(flag == -1) Left[whom] = i;
				else Right[whom] = i;
			}
			F(l,i-1,i,-1);
			F(i+1,r,i,+1);
			return;
		}
	}
	assert(false);
	// cout << l << " " << r << " " << whom << " " << flag << "\n";
}

int solve(int n, int *L, int *R) {
	// query(x, x, x, y) == 1 -> x is parent of y
	root = -1;
	Left.resize(n,-1);
	Right.resize(n,-1);
	F(0, n-1);
	for(int i = 0; i < n; i ++) L[i] = Left[i];
	for(int i = 0; i < n; i ++) R[i] = Right[i];
	Left.clear();
	Right.clear();
	return root;
}

• Subtask 1: 37 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39