#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int A[MAXN];
int nx[MAXN], pv[MAXN];
int as[MAXN];
int idx[MAXN];
bool boring(int s, int e) {
priority_queue<int> mx, mxt;
priority_queue<int, vector<int>, greater<int> > mn, mnt;
//printf("boring(%d, %d)\n", s, e);
for(int i = s; i <= e; i++) if(pv[i] < s && nx[i] > e) {
mx.push(i);
mn.push(i);
}
while(!mx.empty()) {
if(mn.top() - s < e - mx.top()) {
int t = mn.top();
mn.pop();
mxt.push(t);
for(int i = s; i < t; i++) if(nx[i] <= e && nx[nx[i]] > e) {
mn.push(nx[i]);
mx.push(nx[i]);
}
if(boring(s, t - 1)) return true;
s = t + 1;
}
else {
int t = mx.top();
mx.pop();
mnt.push(t);
for(int i = t + 1; i <= e; i++) if(pv[i] >= s && pv[pv[i]] < s) {
mn.push(pv[i]);
mx.push(pv[i]);
}
if(boring(t + 1, e)) return true;
e = t - 1;
}
while(!mxt.empty() && mx.top() == mxt.top()) {
mx.pop();
mxt.pop();
}
while(!mnt.empty() && mn.top() == mnt.top()) {
mn.pop();
mnt.pop();
}
}
return s <= e;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while(T--) {
//printf("*\n");
int N;
cin >> N;
for(int i = 0; i < N; i++) cin >> A[i];
for(int i = 0; i < N; i++) as[i] = A[i];
sort(as, as + N);
for(int i = 0; i < N; i++) A[i] = lower_bound(as, as + N, A[i]) - as;
for(int i = 0; i < N; i++) {
idx[i] = -1;
nx[i] = N;
}
for(int i = 0; i < N; i++) {
if(idx[A[i]] != -1) nx[idx[A[i]]] = i;
pv[i] = idx[A[i]];
idx[A[i]] = i;
}
//for(int i = 0; i < N; i++) printf("(%d, %d) ", pv[i], nx[i]);
//printf("\n");
if(boring(0, N - 1)) cout << "boring\n";
else cout << "non-boring\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
145 ms |
1092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
