oj.uz

Submission #637478

# Submission time Handle Problem Language Result Execution time Memory
637478 2022-09-02T04:22:33 Z GusterGoose27 popa (BOI18_popa) C++11
100 / 100
 97 ms 416 KB 
#include "popa.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1000;
bool lr_par[MAXN]; // when we queried i, i+1, was it i or i+1
int n;
pii range[MAXN];
int rt;
int *l;
int *r;
// int seq[MAXN];

// int gcd(int a, int b) {
// 	if (a > b) return gcd(b, a);
// 	if (a == 0) return b;
// 	return gcd(b%a, a);
// }

// bool query(int a, int b, int c, int d) {
// 	int gcd1 = seq[a];
// 	for (int i = a+1; i <= b; i++) gcd1 = gcd(gcd1, seq[i]);
// 	int gcd2 = seq[c];
// 	for (int i = c+1; i <= d; i++) gcd2 = gcd(gcd2, seq[i]);
// 	return gcd1 == gcd2;
// }

void prune(int i) {
	if (range[i] == pii(0, n-1)) {
		rt = i;
		return;
	}
	if (range[i].first == 0) {
		int next = range[i].second+1;
		l[next] = i;
		range[next].first = range[i].first;
		if (r[next] >= 0 || next == n-1 || lr_par[next]) prune(next);
		return;
	}
	if (range[i].second == n-1) {
		int next = range[i].first-1;
		r[next] = i;
		range[next].second = range[i].second;
		if (l[next] >= 0 || next == 0 || !lr_par[next-1]) prune(next);
		return;
	}
	if (query(range[i].first-1, range[i].second+1, range[i].first-1, range[i].first-1)) { // go right
		int next = range[i].second+1;
		l[next] = i;
		range[next].first = range[i].first;
		if (r[next] >= 0 || next == n-1 || lr_par[next]) prune(next);
		return;
	}
	int next = range[i].first-1;
	r[next] = i;
	range[next].second = range[i].second;
	if (l[next] >= 0 || next == 0 || !lr_par[next-1]) prune(next);
}

int solve(int N, int *Left, int *Right) {
	l = Left;
	r = Right;
	n = N;
	for (int i = 0; i < n-1; i++) {
		lr_par[i] = query(i, i+1, i+1, i+1);
	}
	fill(l, l+n, -1);
	fill(r, r+n, -1);
	for (int i = 0; i < n; i++) range[i] = pii(i, i);
	for (int i = 0; i < n; i++) {
		if (i > 0 && lr_par[i-1]) continue;
		if (i < n-1 && !lr_par[i]) continue;
		prune(i);
	}
	return rt;
}

// int main() {
// 	int N; cin >> N;
// 	for (int i = 0; i < N; i++) cin >> seq[i];
// 	int *Left = new int[N];
// 	int *Right = new int[N];
// 	cout << "root: " << solve(N, Left, Right) << "\n";
// 	for (int i = 0; i < N; i++) {
// 		cout << i << ": " << Left[i] << " " << Right[i] << "\n";
// 	}
// }

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 8 ms 208 KB Output is correct
3 Correct 9 ms 208 KB Output is correct
4 Correct 10 ms 208 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 296 KB Output is correct
2 Correct 97 ms 296 KB Output is correct
3 Correct 27 ms 292 KB Output is correct
4 Correct 82 ms 416 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 300 KB Output is correct
2 Correct 86 ms 296 KB Output is correct
3 Correct 59 ms 300 KB Output is correct
4 Correct 79 ms 296 KB Output is correct