oj.uz

Submission #867528

# Submission time Handle Problem Language Result Execution time Memory
867528 2023-10-28T15:06:26 Z 42kangaroo popa (BOI18_popa) C++17
100 / 100
 46 ms 684 KB 
//
// Created by 42kangaroo on 28/10/2023.
//
#include "bits/stdc++.h"
#include "popa.h"

using namespace std;

struct Node {
	int p, l, r;
};

int solve(int N, int* Left, int* Right) {
	vector<Node> no(N, {-1,-1,-1});
	for (int i = 1; i < N; ++i) {
		int nowN = i - 1;
		int last = nowN;
		while (query(nowN, i, nowN, nowN) == 0) {
			last = nowN;
			nowN = no[nowN].p;
			if (nowN == -1) break;
		}
		if (nowN == -1) {
			no[last].p = i;
			no[i].l = last;
		} else {
			no[i].p =nowN;
			no[i].l = no[nowN].r;
			no[nowN].r = i;
		}
	}
	for (int i = 0; i < N; ++i) {
		Left[i] = no[i].l;
		Right[i] = no[i].r;
	}
	int ro = 0;
	while (no[ro].p != -1) ro = no[ro].p;
	return ro;
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 344 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 684 KB Output is correct
2 Correct 46 ms 592 KB Output is correct
3 Correct 28 ms 452 KB Output is correct
4 Correct 42 ms 428 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 432 KB Output is correct
2 Correct 40 ms 680 KB Output is correct
3 Correct 35 ms 440 KB Output is correct
4 Correct 38 ms 452 KB Output is correct