Guest User

Untitled

a guest
Nov 25th, 2012
264
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #pragma comment(linker,"/STACK:20000000")
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <map>
  7. #include <set>
  8. #include <queue>
  9. #include <algorithm>
  10. #include <cstring>
  11. #include <string>
  12. #include <cassert>
  13. #include <cmath>
  14. #include <ctime>
  15.  
  16. using namespace std;
  17.  
  18. int nextInt(){int x; scanf("%d",&x); return x;}
  19. string problem = "";
  20.  
  21. int a[200005], b[1000005], sh, n;
  22. map<int,vector<int> > poss;
  23.  
  24. pair<map<int,int>,queue<int> > getSet(int l, int r){
  25.     map<int,int> h;
  26.     queue<int> q;
  27.     for (int i=l; i<=r; ++i){
  28.         int x=h[a[i]];
  29.         h[a[i]]=x+1;
  30.     }
  31.     for (int i=l; i<=r; ++i) if (h[a[i]]==1) q.push(a[i]);
  32.     return make_pair(h, q);
  33. }
  34.  
  35. inline int getpos(int ai, int l){
  36.     return *lower_bound(poss[ai].begin(), poss[ai].end(), l);
  37. }
  38.  
  39. bool can(int l, int r, pair<map<int,int>,queue<int> >& cnt){
  40.     if (l>=r) return true;
  41.     int un = -1;
  42.     while (!cnt.second.empty()){
  43.         int val = cnt.second.front();
  44.         cnt.second.pop();
  45.         if (cnt.first[val] != 1) continue;
  46.         un = val;
  47.         break;
  48.     }
  49.     if (un==-1) return false;
  50.     int pos = getpos(un, l);
  51.     bool ok1=false, ok2=false;
  52.     if (pos-l < r-pos){
  53.         pair<map<int,int>,queue<int> > s1=getSet(l, pos-1);
  54.         ok1=can(l, pos-1,s1);
  55.         for (int i=l; i<=pos-1; ++i){
  56.             int x=cnt.first[a[i]];
  57.             --x;
  58.             cnt.first[a[i]]=x;
  59.             if (x == 1){
  60.                 cnt.second.push(a[i]);
  61.             }
  62.         }
  63.         ok2=can(pos+1, r, cnt);
  64.     } else {
  65.         pair<map<int,int>,queue<int> > s1=getSet(pos+1, r);
  66.         ok1=can(pos+1, r,s1);
  67.         for (int i=pos+1; i<=r; ++i){
  68.             int x=cnt.first[a[i]];
  69.             --x;
  70.             cnt.first[a[i]]=x;
  71.             if (x == 1){
  72.                 cnt.second.push(a[i]);
  73.             }
  74.         }
  75.         ok2=can(l, pos-1, cnt);
  76.     }
  77.     return ok1&&ok2;
  78. }
  79.  
  80. void solve(){
  81.     int t=nextInt();
  82.  
  83.     while (t--){
  84.         poss=map<int,vector<int> >();
  85.         scanf("%d", &n);
  86.         for (int i=0; i<n; ++i) {
  87.             scanf("%d",&a[i]);
  88.             poss[a[i]].push_back(i);
  89.         }
  90.         pair<map<int,int>,queue<int> > s1=getSet(0, n-1);
  91.         if (can(0, n-1, s1)) printf("non-boring\n");
  92.         else printf("boring\n");
  93.     }
  94. }
  95.  
  96.  
  97. int main(){
  98.  
  99. #ifdef KP_HOME
  100.     freopen("input.txt","r",stdin);
  101.     //freopen("output.txt","w",stdout);
  102. #else
  103.     //freopen((problem+".in").c_str(),"r",stdin);
  104.     //freopen((problem+".out").c_str(),"w",stdout);
  105.     //freopen("input.txt","r",stdin);
  106.     //freopen("output.txt","w",stdout);
  107. #endif
  108.  
  109.     solve();
  110.  
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment