結果

問題 No.2148 ひとりUNO
コンテスト
ユーザー ei1333333
提出日時 2022-11-18 22:36:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,460 bytes
コンパイル時間 2,072 ms
コンパイル使用メモリ 210,888 KB
最終ジャッジ日時 2025-02-08 22:04:05
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

const string colors = "RGBY";

const string patterns[] = {
    "A",
    "AB",
    "AAB",
    "ABB",
    "ABC",
    "AABB",
    "AABC",
    "ABBC",
    "ABCC",
    "ABCD",
    "AABBC",
    "AABCC",
    "AABCD",
    "ABBBC",
    "ABBCC",
    "ABBCD",
    "ABCCD",
    "ABCDD",
    "AABBBC",
    "AABBCC",
    "AABBCD",
    "AABCCD",
    "AABCDD",
    "ABBBCC",
    "ABBBCD",
    "ABBCCD",
    "ABBCDD",
    "ABCCBD",
    "ABCCCD",
    "ABCCDD",
    "ABCDDB",
    "AABBBCC",
    "AABBBCD",
    "AABBCCD",
    "AABBCDD",
    "AABCCBD",
    "AABCCCD",
    "AABCCDD",
    "AABCDDB",
    "ABBBCCD",
    "ABBBCDD",
    "ABBCCCD",
    "ABBCCDD",
    "ABCCBDD",
    "ABCCCBD",
    "ABCCCDD",
    "ABCCDDB",
    "ABCDDBB",
    "ABCDDDB",
    "AABBBCCD",
    "AABBBCDD",
    "AABBCCCD",
    "AABBCCDD",
    "AABCCBDD",
    "AABCCCBD",
    "AABCCCDD",
    "AABCCDDB",
    "AABCDDBB",
    "AABCDDDB",
    "ABBBCCCD",
    "ABBBCCDD",
    "ABBCCCDD",
    "ABCCBDDB",
    "ABCCCBDD",
    "ABCCCDDB",
    "ABCCDDBB",
    "ABCCDDDB",
    "ABCDDBBD",
    "ABCDDDBB",
    "AABBBCCCD",
    "AABBBCCDD",
    "AABBCCCDD",
    "AABCCBDDB",
    "AABCCCBDD",
    "AABCCCDDB",
    "AABCCDDBB",
    "AABCCDDDB",
    "AABCDDBBD",
    "AABCDDDBB",
    "ABBBCCCDD",
    "ABCCBDDDB",
    "ABCCCBDDB",
    "ABCCCDDBB",
    "ABCCCDDDB",
    "ABCCDDBBD",
    "ABCCDDDBB",
    "AABBBCCCDD",
    "AABCCBDDDB",
    "AABCCCBDDB",
    "AABCCCDDBB",
    "AABCCCDDDB",
    "AABCCDDBBD",
    "AABCCDDDBB",
    "ABCCCBDDDB",
    "ABCCCDDBBD",
    "ABCCCDDDBB",
    "AABCCCBDDDB",
    "AABCCCDDBBD",
    "AABCCCDDDBB",
};

void test() {
  int N;
  cin >> N;
  vector< int > C(N), D(N);
  for (int i = 0; i < N; i++) {
    char c;
    cin >> c >> D[i];
    C[i] = colors.find(c);
  }

  vector< int > perm{0, 1, 2, 3};
  do {
    vector< int > cnt(1 << 4);
    {
      map< int, int > mp;
      for (int i = 0; i < N; i++) {
        mp[D[i]] |= 1 << perm[C[i]];
      }
      for (auto &p: mp) {
        cnt[p.second]++;
      }
    }
    for (auto& pattern: patterns) {
      vector< int > old_parts;
      for (auto &c: pattern) {
        int p = (c - 'A');
        if (old_parts.empty() or ((old_parts.back() >> p) & 1)) {
          old_parts.emplace_back();
        }
        old_parts.back() |= 1 << p;
      }
      vector< int > parts;
      for(auto& c : old_parts) {
        if(c == 1 or c == 2 or c == 4 or c == 8) parts.emplace_back(c);
      }
      for(auto& c : old_parts) {
        if(c != 1 and c != 2 and c != 4 and c != 8) parts.emplace_back(c);
      }
      auto dfs = [&](auto &dfs, int idx) -> bool {
        if (idx == -1) {
          return *max_element(cnt.begin(), cnt.end()) == 0;
        }
        bool type = __builtin_popcount(parts[idx]) == 1;
        for (int i = 0; i < cnt.size(); i++) {
          if (cnt[i] > 0 and (parts[idx] & i) == parts[idx]) {
            int sub = type ? cnt[i] : 1;
            cnt[i] -= sub;
            if (i != parts[idx]) cnt[i ^ parts[idx]] += sub;
            if (dfs(dfs, idx - 1)) return true;
            if (i != parts[idx]) cnt[i ^ parts[idx]] -= sub;
            cnt[i] += sub;
          }
        }
        return false;
      };
      if (dfs(dfs, (int) parts.size() - 1)) {
        cout << "YES" << endl;
        return;
      }
    }
  } while (next_permutation(perm.begin(), perm.end()));
  cout << "NO" << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    test();
  }
}
0