oj.uz

Submission #862134

# Submission time Handle Problem Language Result Execution time Memory
862134 2023-10-17T14:31:58 Z maks007 popa (BOI18_popa) C++14
37 / 100
 157 ms 596 KB 
#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.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 428 KB Output is correct
2 Correct 47 ms 596 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 32 ms 436 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 428 KB too many queries
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 344 KB too many queries
2 Halted 0 ms 0 KB -