Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker,"/STACK:20000000")
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <cassert>
- #include <cmath>
- #include <ctime>
- using namespace std;
- int nextInt(){int x; scanf("%d",&x); return x;}
- string problem = "";
- int a[200005], b[1000005], sh, n;
- map<int,vector<int> > poss;
- pair<map<int,int>,queue<int> > getSet(int l, int r){
- map<int,int> h;
- queue<int> q;
- for (int i=l; i<=r; ++i){
- int x=h[a[i]];
- h[a[i]]=x+1;
- }
- for (int i=l; i<=r; ++i) if (h[a[i]]==1) q.push(a[i]);
- return make_pair(h, q);
- }
- inline int getpos(int ai, int l){
- return *lower_bound(poss[ai].begin(), poss[ai].end(), l);
- }
- bool can(int l, int r, pair<map<int,int>,queue<int> >& cnt){
- if (l>=r) return true;
- int un = -1;
- while (!cnt.second.empty()){
- int val = cnt.second.front();
- cnt.second.pop();
- if (cnt.first[val] != 1) continue;
- un = val;
- break;
- }
- if (un==-1) return false;
- int pos = getpos(un, l);
- bool ok1=false, ok2=false;
- if (pos-l < r-pos){
- pair<map<int,int>,queue<int> > s1=getSet(l, pos-1);
- ok1=can(l, pos-1,s1);
- for (int i=l; i<=pos-1; ++i){
- int x=cnt.first[a[i]];
- --x;
- cnt.first[a[i]]=x;
- if (x == 1){
- cnt.second.push(a[i]);
- }
- }
- ok2=can(pos+1, r, cnt);
- } else {
- pair<map<int,int>,queue<int> > s1=getSet(pos+1, r);
- ok1=can(pos+1, r,s1);
- for (int i=pos+1; i<=r; ++i){
- int x=cnt.first[a[i]];
- --x;
- cnt.first[a[i]]=x;
- if (x == 1){
- cnt.second.push(a[i]);
- }
- }
- ok2=can(l, pos-1, cnt);
- }
- return ok1&&ok2;
- }
- void solve(){
- int t=nextInt();
- while (t--){
- poss=map<int,vector<int> >();
- scanf("%d", &n);
- for (int i=0; i<n; ++i) {
- scanf("%d",&a[i]);
- poss[a[i]].push_back(i);
- }
- pair<map<int,int>,queue<int> > s1=getSet(0, n-1);
- if (can(0, n-1, s1)) printf("non-boring\n");
- else printf("boring\n");
- }
- }
- int main(){
- #ifdef KP_HOME
- freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- #else
- //freopen((problem+".in").c_str(),"r",stdin);
- //freopen((problem+".out").c_str(),"w",stdout);
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- #endif
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment