fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int mex(const vector<int>& v) {
  5.     set<int> s(v.begin(), v.end());
  6.     for (int i = 0; i <= 4; ++i)
  7.         if (!s.count(i)) return i;
  8.     return 5;
  9. }
  10.  
  11. bool is_good(vector<int> &triple) {
  12.     int x = *min_element(triple.begin(), triple.end());
  13.     int y = *max_element(triple.begin(), triple.end());
  14.     return mex(triple) == y - x;
  15. }
  16.  
  17. bool can_make_good(vector<int>& a) {
  18.     int n = a.size();
  19.     for (int i = 0; i + 2 < n; ++i) {
  20.         vector<int> sub = {a[i], a[i+1], a[i+2]};
  21.         bool ok = false;
  22.  
  23.         // Check if there are any -1s
  24.         if (count(sub.begin(), sub.end(), -1) == 0) {
  25.             if (!is_good(sub)) return false;
  26.             continue;
  27.         }
  28.  
  29.         // Try all combinations for -1s using values 0,1,2,3
  30.         for (int x = 0; x <= 3; ++x)
  31.             for (int y = 0; y <= 3; ++y)
  32.                 for (int z = 0; z <= 3; ++z) {
  33.                     vector<int> t = sub;
  34.                     if (t[0] == -1) t[0] = x;
  35.                     if (t[1] == -1) t[1] = y;
  36.                     if (t[2] == -1) t[2] = z;
  37.                     if (is_good(t)) {
  38.                         ok = true;
  39.                         goto next;
  40.                     }
  41.                 }
  42.     next:
  43.         if (!ok) return false;
  44.     }
  45.     return true;
  46. }
  47.  
  48. int main() {
  49.     int t; cin >> t;
  50.     while (t--) {
  51.         int n; cin >> n;
  52.         vector<int> a(n);
  53.         for (int &x : a) cin >> x;
  54.         cout << (can_make_good(a) ? "YES" : "NO") << '\n';
  55.     }
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
8
3
-1 -1 -1
5
1 1 1 1 0
6
5 5 1 -1 -1 1
4
-1 -1 0 -1
4
-1 1 1 -1
3
3 3 -1
5
0 0 0 0 0
7
3 0 1 4 -1 2 3
stdout
copy 
YES
NO
NO
NO
YES
YES
NO
NO
https://ideone.com/Wk7Nz8
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!