#include <bits/stdc++.h>
using namespace std;
using mii = map<int, int>;
#define X first
#define Y second
int A[200009];
vector<int> S[200009];
bool ok;
int findany(int v, int s, int e) {
int ret = *lower_bound(S[v].begin(), S[v].end(), s);
assert(s <= ret && ret <= e);
return ret;
}
void solve(int s, int e, mii &mp, set<int> &O) {
if(s > e) return;
if(O.empty()) {
ok = 0;
return;
}
int u = *O.begin(), p = findany(u, s, e);
O.erase(O.begin()); mp.erase(u);
int m = s+e >> 1;
mii _mp; set<int> _O;
if(p <= m) {
for(int i=s; i<p; i++) {
++_mp[A[i]];
int v = --mp[A[i]];
if(v == 1) O.insert(A[i]);
if(v == 0) {
O.erase(A[i]);
mp.erase(A[i]);
}
}
for(auto& it: _mp) if(it.Y == 1) _O.insert(it.X);
solve(s, p-1, _mp, _O);
solve(p+1, e, mp, O);
}
else {
for(int i=p+1; i<e; i++) {
++_mp[A[i]];
int v = --mp[A[i]];
if(v == 1) O.insert(A[i]);
if(v == 0) {
O.erase(A[i]);
mp.erase(A[i]);
}
}
for(auto& it: _mp) if(it.Y == 1) _O.insert(it.X);
solve(s, p-1, mp, O);
solve(p+1, e, _mp, _O);
}
}
int main() {
int T; scanf("%d",&T);
while(T--) {
vector<int> T;
int N; scanf("%d",&N);
for(int i=1; i<=N; i++) {
scanf("%d",&A[i]);
T.push_back(A[i]);
}
sort(T.begin(), T.end()); T.resize(unique(T.begin(), T.end()) - T.begin());
mii mp; set<int> O;
for(int i=1; i<=T.size(); i++) {
S[i].clear();
S[i].shrink_to_fit();
}
for(int i=1; i<=N; i++) {
A[i] = lower_bound(T.begin(), T.end(), A[i]) - T.begin() + 1;
S[A[i]].push_back(i);
++mp[A[i]];
}
for(auto& it: mp) if(it.Y == 1) O.insert(it.X);
ok = 1; solve(1, N, mp, O);
puts(ok ? "non-boring" : "boring");
}
return 0;
}
Compilation message
D.cpp: In function 'void solve(int, int, mii&, std::set<int>&)':
D.cpp:25:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
D.cpp: In function 'int main()':
D.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<=T.size(); i++) {
~^~~~~~~~~~
D.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int T; scanf("%d",&T);
~~~~~^~~~~~~~~
D.cpp:61:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N; scanf("%d",&N);
~~~~~^~~~~~~~~
D.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&A[i]);
~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
15 ms |
9976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
