# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
652887 | lto5 | Non-boring sequences (CERC12_D) | C++14 | 5055 ms | 3392 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
template <typename T> inline void read (T &x) {
char ch;
while (!isdigit(ch = getchar()) && ch != '-') ;
bool sign = ch == '-';
x = isdigit(ch) ? ch - '0' : 0;
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
if (sign)
x = -x;
}
template <typename T> inline void write_pos (T x) {
if (x > 9) {
write_pos(x / 10);
}
putchar(x % 10 + '0');
}
template <typename T> inline void write (T x) {
if (x < 0)
putchar('-'), x = -x;
write_pos(x);
}
int n;
int a[N];
int b[N];
int cnt[N];
void read_input() {
read(n);
for (int i = 1; i <= n; i++) {
read(a[i]);
b[i] = a[i];
}
}
bool boring (int L, int R, int turn = 0) {
if (L >= R)
return false;
for (int i = L; i <= R; i++)
cnt[a[i]] = 0;
for (int i = L; i <= R; i++)
cnt[a[i]]++;
if (!turn) {
for (int i = L; i <= R; i++)
if (cnt[a[i]] == 1)
return boring(L, i - 1, turn^1) || boring(i + 1, R, turn);
}
else {
for (int i = R; i >= L; i--)
if (cnt[a[i]] == 1)
return boring(L, i - 1, turn^1) || boring(i + 1, R, turn);
}
return true;
}
void solve() {
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
cnt[a[i]] = 0;
}
puts(!boring(1, n) ? "non-boring" : "boring");
}
int main() {
int t;
read(t);
while (t--) {
read_input();
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |