fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void solve() {
  8.     int n;
  9.     cin >> n;
  10.     vector<int> a(n);
  11.     for (int i = 0; i < n; ++i) {
  12.         cin >> a[i];
  13.     }
  14.  
  15.     vector<int> sorted_a = a;
  16.     sort(sorted_a.begin(), sorted_a.end());
  17.     sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
  18.     for (int& x : a) {
  19.         x = lower_bound(sorted_a.begin(), sorted_a.end(), x) - sorted_a.begin();
  20.     }
  21.  
  22.     int num_distinct = sorted_a.size();
  23.     vector<int> blocks(num_distinct, 0);
  24.     int bad_left = -1;
  25.     vector<int> seen(num_distinct, 0);
  26.  
  27.     for (int i = 0; i < n; ++i) {
  28.         if (i == 0 || a[i] != a[i - 1]) {
  29.             blocks[a[i]]++;
  30.             if (blocks[a[i]] >= 4) {
  31.                 cout << "NO\n";
  32.                 return;
  33.             }
  34.             if (bad_left == -1 && seen[a[i]]) {
  35.                 bad_left = i;
  36.             }
  37.             seen[a[i]] = 1;
  38.         }
  39.     }
  40.  
  41.     if (bad_left == -1) {
  42.         cout << "YES\n";
  43.         return;
  44.     }
  45.  
  46.     int bad_right = -1;
  47.     vector<int> seen2(num_distinct, 0);
  48.     for (int i = n - 1; i >= 0; --i) {
  49.         if (i == n - 1 || a[i] != a[i + 1]) {
  50.             if (bad_right == -1 && seen2[a[i]]) {
  51.                 bad_right = i;
  52.             }
  53.             seen2[a[i]] = 1;
  54.         }
  55.     }
  56.  
  57.     int v = a[bad_left];
  58.     int u = a[bad_right];
  59.  
  60.     auto get_candidates = [&](int val) {
  61.         vector<int> c;
  62.         int L = -1;
  63.         for (int i = 0; i <= n; ++i) {
  64.             if (i < n && a[i] == val) {
  65.                 if (L == -1) L = i;
  66.             } else {
  67.                 if (L != -1) {
  68.                     int R = i - 1;
  69.                     for (int x : {L - 1, L, L + 1, R - 1, R, R + 1}) {
  70.                         if (x >= 0 && x < n) c.push_back(x);
  71.                     }
  72.                     L = -1;
  73.                 }
  74.             }
  75.         }
  76.         return c;
  77.     };
  78.  
  79.     vector<int> cand;
  80.     vector<int> cv = get_candidates(v);
  81.     vector<int> cu = get_candidates(u);
  82.     cand.insert(cand.end(), cv.begin(), cv.end());
  83.     cand.insert(cand.end(), cu.begin(), cu.end());
  84.  
  85.     sort(cand.begin(), cand.end());
  86.     cand.erase(unique(cand.begin(), cand.end()), cand.end());
  87.  
  88.     int token = 0;
  89.     vector<int> seen_check(num_distinct, 0);
  90.     auto check = [&](const vector<int>& arr) {
  91.         token++;
  92.         for (int i = 0; i < n; ++i) {
  93.             if (i > 0 && arr[i] == arr[i - 1]) continue;
  94.             if (seen_check[arr[i]] == token) return false;
  95.             seen_check[arr[i]] = token;
  96.         }
  97.         return true;
  98.     };
  99.  
  100.     for (int i = 0; i < cand.size(); ++i) {
  101.         for (int j = i + 1; j < cand.size(); ++j) {
  102.             if (a[cand[i]] == a[cand[j]]) continue;
  103.             swap(a[cand[i]], a[cand[j]]);
  104.             if (check(a)) {
  105.                 cout << "YES\n";
  106.                 return;
  107.             }
  108.             swap(a[cand[i]], a[cand[j]]);
  109.         }
  110.     }
  111.     cout << "NO\n";
  112. }
  113.  
  114. int main() {
  115.     ios_base::sync_with_stdio(false);
  116.     cin.tie(NULL);
  117.     int t;
  118.     if (cin >> t) {
  119.         while (t--) {
  120.             solve();
  121.         }
  122.     }
  123.     return 0;
  124. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
7
3
1 2 1
2
7 7
6
1 2 3 1 2 3
6
1 1 2 3 2 3
7
1 2 3 1 2 3 4
6
1 2 1 2 1 1
6
1 2 2 3 3 1
stdout
copy 
YES
YES
NO
YES
NO
YES
NO
https://ideone.com/GsWEEm
language:
C++14 (gcc 8.3)
created:
1 hour 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!