oj.uz

Submission #61931

# Submission time Handle Problem Language Result Execution time Memory
61931 2018-07-27T05:43:38 Z ainta(#1792) popa (BOI18_popa) C++11
37 / 100
 175 ms 468 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 1010
#include "popa.h"
using namespace std;
int L[N_], R[N_], C[N_];
int solve(int N, int* Left, int* Right) {
	int i, j;
	for (i = 0; i < N; i++) {
		int b = 0, e = i, r = i, mid;
		while (b <= e) {
			mid = (b + e) >> 1;
			if (query(i, i, mid, i))r = mid, e = mid - 1;
			else b = mid + 1;
		}
		L[i] = r;
		b = i, e = N - 1, r = i;
		while (b <= e) {
			mid = (b + e) >> 1;
			if (query(i, i, i, mid))r = mid, b = mid + 1;
			else e = mid - 1;
		}
		R[i] = r;
		C[i] = R[i] - L[i];
	}
	int root = -1;
	for (i = 0; i < N; i++) {
		Left[i] = Right[i] = -1;
		for (j = 0; j < N; j++){
			if (C[i] > C[j]) {
				if (L[i] == L[j] && (Left[i] == -1 || C[j] > C[Left[i]]))Left[i] = j;
				if (R[i] == R[j] && (Right[i] == -1 || C[j] > C[Right[i]]))Right[i] = j;
			}
		}
		if (C[i] == N - 1)root = i;
	}
	return root;
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 248 KB Output is correct
2 Correct 63 ms 468 KB Output is correct
3 Correct 64 ms 468 KB Output is correct
4 Correct 53 ms 468 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 468 KB not a valid binary tree
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

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