Submission #651983

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
651983	2022-10-21T02:29:16 Z	ducbrick	Non-boring sequences (CERC12_D)	C++17	0 / 1	5000 ms	2008 KB

D

#include <bits/stdc++.h>
using namespace std;

template <typename T> inline void read(T &n) {
  char digit;

  do
    digit = getchar();
  while (isdigit(digit) == false && digit != '-');

  bool negative = (digit == '-');

  if (negative)
    digit = getchar();

  n = 0;

  do
    n = n * 10 + digit - '0',
    digit = getchar();
  while (isdigit(digit));

  if (negative)
    n = -n;
}

const int MAX_N = 2e5;

int a[MAX_N + 1];

void compress(int n) {
  vector <int> v;

  for (int i = 1; i <= n; i++)
    v.push_back(a[i]);

  sort(v.begin(), v.end());

  for (int i = 1; i <= n; i++)
    a[i] = upper_bound(v.begin(), v.end(), a[i])
         - v.begin();
}

int f[MAX_N + 1];

bool ok(int l, int r) {
  if (r <= l)
    return true;

  for (int i = l; i <= r; i++)
    f[a[i]] = 0;

  for (int i = l; i <= r; i++)
    f[a[i]]++;
  
  // if (l == 1 && r == 10)
  //   for (int i = l; i <= r; i++)
  //     if (f[a[i]] == 1)
  //       cerr << i << ' ';

  vector <int> p;

  for (int i = l; i <= r; i++)
    if (f[a[i]] == 1) 
      p.push_back(i);

  if (p.empty())
    return false;

  if (ok(l, p.front() - 1) == false)
    return false;

  if (ok(p.back() + 1, r) == false)
    return false;

  for (int i = 1; i < p.size(); i++)
    if (ok(p[i - 1] + 1, p[i] - 1) == false)
      return false;

  return true;
}

string solve() {
  int n;
  read(n);

  for (int i = 1; i <= n; i++)
    read(a[i]);

  compress(n);

  // for (int i = 1; i <= n; i++)
  //   cerr << a[i] << ' ';

  return (ok(1, n) ? "non-boring" : "boring");
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  

  int t;
  read(t);

  while (t--)
    cout << solve() << '\n';
}

Compilation message

D.cpp: In function 'bool ok(int, int)':
D.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = 1; i < p.size(); i++)
      |                   ~~^~~~~~~~~~

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	1104 KB	Output is correct
2	Execution timed out	5050 ms	2008 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-