Submission #135916

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135916	2019-07-24T13:31:30 Z	model_code	Non-boring sequences (CERC12_D)	C++11	1 / 1	416 ms	10488 KB

D

// CERC 2012
// Problem D: Non-boring sequences
// Model solution. O(n lg n)
// Author: Adam Polak

#include <algorithm>
#include <iostream>
using namespace std;

#define prev Prev
#define next Next

const int MAXN = 200000;

int n, a[MAXN], values[MAXN];
int prev[MAXN], next[MAXN], last[MAXN];

bool IsBoring(int beg, int end) {
  if (beg == end) return false;
  for (int i = 0; i < (end - beg); ++i) {
    int mid = ((i & 1) ? beg + i / 2 : end - 1 - i / 2);
    if (prev[mid] < beg && next[mid] >= end)
      return IsBoring(beg, mid) || IsBoring(mid+1, end);
  }
  return true;
}

int main() {
  ios_base::sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      values[i] = a[i];
    }
    sort(values, values + n);
    int m = unique(values, values + n) - values;
    for (int i = 0; i < n; ++i)
      a[i] = lower_bound(values, values + m, a[i]) - values;

    for (int i = 0; i < m; ++i) last[i] = -1;
    for (int i = 0; i < n; ++i) {
      prev[i] = last[a[i]];
      last[a[i]] = i;
    }
    for (int i = 0; i < m; ++i) last[i] = n;
    for (int i = n-1; i >= 0; --i) {
      next[i] = last[a[i]];
      last[a[i]] = i;
    }

    cout << (IsBoring(0, n) ? "boring\n" : "non-boring\n");
   }
  return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	335 ms	1016 KB	Output is correct
2	Correct	139 ms	3224 KB	Output is correct
3	Correct	165 ms	10488 KB	Output is correct
4	Correct	85 ms	6904 KB	Output is correct
5	Correct	416 ms	4828 KB	Output is correct
6	Correct	321 ms	3628 KB	Output is correct
7	Correct	244 ms	3448 KB	Output is correct