Submission #637477

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
637477	2022-09-02T04:22:13 Z	GusterGoose27	popa (BOI18_popa)	C++11	Compilation error	0 ms	0 KB

popa

#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";
// 	}
// }

Compilation message

popa.cpp:23:6: error: ambiguating new declaration of 'bool query(int, int, int, int)'
   23 | bool query(int a, int b, int c, int d) {
      |      ^~~~~
In file included from popa.cpp:1:
popa.h:4:5: note: old declaration 'int query(int, int, int, int)'
    4 | int query(int a, int b, int c, int d);
      |     ^~~~~