aoapc-UVA-Answer/Chapter-8/UVA-1608.cpp at master · jzplp/aoapc-UVA-Answer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <map>
#define MAXN 200005
using namespace std;

int arr[MAXN];
int prevArr[MAXN];
int nextArr[MAXN];
int n;
map<int, int> mp;

void init()
{
  int i, j, k;
  mp.clear();
  for (i = 1; i <= n; ++i)
  {
    if (!mp[arr[i]])
      prevArr[i] = 0;
    else
      prevArr[i] = mp[arr[i]];
    mp[arr[i]] = i;
  }
  mp.clear();
  for (i = n; i >= 1; --i)
  {
    if (!mp[arr[i]])
      nextArr[i] = n + 10;
    else
      nextArr[i] = mp[arr[i]];
    mp[arr[i]] = i;
  }
}

bool computed(int beg, int end)
{
  if (beg >= end)
    return true;
  int i, endi = (end - beg) / 2 + 1;
  for (i = 0; i <= endi; ++i)
  {
    if (prevArr[beg + i] < beg && nextArr[beg + i] > end)
      return computed(beg, beg + i - 1) && computed(beg + i + 1, end);
    if (prevArr[end - i] < beg && nextArr[end - i] > end)
      return computed(beg, end - i - 1) && computed(end - i + 1, end);
  }
  return false;
}

int main()
{
  int t, i, j;
  scanf("%d", &t);
  while (t--)
  {
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
      scanf("%d", &arr[i]);
    init();
    if (computed(1, n))
      printf("non-boring\n");
    else
      printf("boring\n");
  }
  return 0;
}