| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 637477 | 2022-09-02T04:22:13 Z | GusterGoose27 | popa (BOI18_popa) | C++11 | 0 ms | 0 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";
// }
// }