QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300152#4859. Poker Game: Constructionhos_lyricAC ✓231ms3960kbC++1419.8kb2024-01-07 19:13:062024-01-07 19:13:08

Judging History

你现在查看的是最新测评结果

  • [2024-01-07 19:13:08]
  • 评测
  • 测评结果:AC
  • 用时:231ms
  • 内存:3960kb
  • [2024-01-07 19:13:06]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int bsr(int a) {
  return 31 - __builtin_clz(a);
}

// Returns the submask containing highest k bits set.
// Returns -1 instead if  popcnt(a) < k.
int highBits(int a, int k) {
  int b = 0;
  for (int i = 0; i < k; ++i) {
    if (!a) return -1;
    b |= 1 << (31 - __builtin_clz(a));
    a &= ~b;
  }
  return b;
}

constexpr char RANKS_STR[16] = "0123456789TJQKA";
constexpr char SUITS_STR[5] = "CDHS";
enum Poker {
  HIGH_CARD,
  ONE_PAIR,
  TWO_PAIR,
  THREE_OF_A_KIND,
  STRAIGHT,
  FLUSH,
  FULL_HOUSE,
  FOUR_OF_A_KIND,
  STRAIGHT_FLUSH,
};
constexpr char POKER_STR[9][20] = {
  "HIGH_CARD",
  "ONE_PAIR",
  "TWO_PAIR",
  "THREE_OF_A_KIND",
  "STRAIGHT",
  "FLUSH",
  "FULL_HOUSE",
  "FOUR_OF_A_KIND",
  "STRAIGHT_FLUSH",
};

// Parses a card in a format as "2C" or "C2".
// Returns  card = 4 (rank - 2) + suit  (2 <= rank <= 14)
int parseCard(const char *str) {
  int r, s;
  for (s = 0; s < 4; ++s) if (SUITS_STR[s] == str[1]) break;
  if (s < 4) {
    // "2C"
    for (r = 2; r < 15; ++r) if (RANKS_STR[r] == str[0]) break;
    assert(r < 15);
  } else {
    // "C2"
    for (s = 0; s < 4; ++s) if (SUITS_STR[s] == str[0]) break;
    assert(s < 4);
    for (r = 2; r < 15; ++r) if (RANKS_STR[r] == str[1]) break;
    assert(r < 15);
  }
  return (r - 2) << 2 | s;
}

// Read a card from standard input.
int readCard() {
  static char buf[3];
  scanf("%s", buf);
  return parseCard(buf);
}

// Transforms a card in a format as "2C" (or "C2" if rev).
string cardString(int card, bool rev = false) {
  const int r = card / 4 + 2, s = card % 4;
  return rev ? (string() + SUITS_STR[s] + RANKS_STR[r]) : (string() + RANKS_STR[r] + SUITS_STR[s]);
}

// Returns the best poker hand with the tie-breaker in [0, 2^20).
//   cards must be distinct.
pair<Poker, int> poker(const vector<int> &cards) {
  assert(cards.size() >= 5);
  // a: ranks for all, bs[suit]: ranks, cs[rank]: count, ds[count]: ranks
  int a = 0, bs[4] = {}, cs[15] = {}, ds[5] = {};
  for (const int card : cards) { const int r = (card >> 2) + 2, s = card & 3; a |= bs[s] |= 1 << r; ++cs[r]; }
  for (int r = 2; r < 15; ++r) ds[cs[r]] |= 1 << r;
  // 8. STRAIGHT_FLUSH: highest (5 for A2345)
  {
    int straightFlush = 0;
    for (int s = 0; s < 4; ++s) straightFlush |= bs[s] & bs[s] << 1 & bs[s] << 2 & bs[s] << 3 & (bs[s] << 4 | bs[s] >> 14 << 5);
    if (straightFlush) return make_pair(STRAIGHT_FLUSH, bsr(straightFlush));
  }
  // 7. FOUR_OF_A_KIND: quadruple, other card
  if (ds[4]) {
    const int r4 = bsr(ds[4]);
    return make_pair(FOUR_OF_A_KIND, r4 << 4 | bsr(a ^ 1 << r4));
  }
  // 6. FULL_HOUSE: triple, pair
  if (ds[3]) {
    const int r3 = bsr(ds[3]);
    const int d = (ds[3] ^ 1 << r3) | ds[2];
    if (d) {
      const int r2 = bsr(d);
      return make_pair(FULL_HOUSE, r3 << 4 | r2);
    }
  }
  // 5. FLUSH: 5 highest cards
  {
    int flush = -1;
    for (int s = 0; s < 4; ++s) { const int h = highBits(bs[s], 5); if (flush < h) flush = h; }
    if (flush >= 0) return make_pair(FLUSH, flush);
  }
  // 4. STRAIGHT: highest (5 for A2345)
  {
    const int straight = a & a << 1 & a << 2 & a << 3 & (a << 4 | a >> 14 << 5);
    if (straight) return make_pair(STRAIGHT, bsr(straight));
  }
  // 3. THREE_OF_A_KIND: triple, 2 highest other cards
  if (ds[3]) {
    const int r3 = bsr(ds[3]);
    return make_pair(THREE_OF_A_KIND, r3 << 16 | highBits(a ^ 1 << r3, 2));
  }
  // 2. TWO_PAIR: larger pair, smaller pair, other card
  // 1. ONE_PAIR: pair, 3 highest other cards
  if (ds[2]) {
    const int r2 = bsr(ds[2]);
    const int d = ds[2] ^ 1 << r2;
    if (d) {
      const int r22 = bsr(d);
      return make_pair(TWO_PAIR, r2 << 8 | r22 << 4 | bsr(a ^ 1 << r2 ^ 1 << r22));
    }
    return make_pair(ONE_PAIR, r2 << 16 | highBits(a ^ 1 << r2, 3));
  }
  // 0. HIGH_CARD: 5 highest cards
  return make_pair(HIGH_CARD, highBits(a, 5));
}

////////////////////////////////////////////////////////////////////////////////


string tos(const vector<int> &C) {
  ostringstream os;
  os << "[";
  for (int i = 0; i < (int)C.size(); ++i) {
    if (i) os << ", ";
    os << cardString(C[i]);
  }
  os << "]";
  return os.str();
}

int simulate(int A0, int A1, int B0, int B1, const vector<int> &C) {
  constexpr int THREE[6 + 1] = {1, 3, 9, 27, 81, 243, 729};
  assert(C.size() == 6);
  vector<int> dp(THREE[6], 2);
  for (int p = THREE[6]; --p >= 0; ) {
    vector<int> xs(6);
    for (int i = 0; i < 6; ++i) xs[i] = p / THREE[i] % 3;
    int cnt[3] = {};
    for (int i = 0; i < 6; ++i) ++cnt[xs[i]];
    if (cnt[1] == 3 && cnt[2] == 3) {
      vector<int> as{A0, A1}, bs{B0, B1};
      for (int i = 0; i < 6; ++i) ((xs[i] == 1) ? as : bs).push_back(C[i]);
      const auto resA = poker(as);
      const auto resB = poker(bs);
      dp[p] = (resA > resB) ? +1 : (resA < resB) ? -1 : 0;
    } else if (cnt[1] == cnt[2]) {
      // A
      dp[p] = -1;
      for (int i = 0; i < 6; ++i) if (!xs[i]) chmax(dp[p], dp[p + THREE[i]]);
    } else if (cnt[1] == cnt[2] + 1) {
      // B
      dp[p] = +1;
      for (int i = 0; i < 6; ++i) if (!xs[i]) chmin(dp[p], dp[p + 2 * THREE[i]]);
    }
  }
  return dp[0];
}

vector<vector<int>> brute(int A0, int A1, int B0, int B1) {
// cerr<<COLOR("33")<<"[brute] "<<cardString(A0)<<" "<<cardString(A1)<<" "<<cardString(B0)<<" "<<cardString(B1)<<COLOR()<<endl;
  constexpr int NUM_TRIES = 100;
  mt19937_64 rng(58);
  vector<vector<int>> ans(3);
  for (int phase = 0; phase < 3; ++phase) {
    int numTries = 0;
    for (int iter = 0; ; ++iter) {
      if (phase == 0 && ans[1 + (+1)].size()) break;
      if (phase == 1 && ans[1 + (-1)].size()) break;
      if (phase == 2 && ans[1 + 0   ].size()) break;
      vector<int> C(6);
      if (phase == 0) {
        // random
        for (int i = 0; i < 6; ++i) {
          C[i] = rng() % 52;
        }
      } else if (phase == 1) {
        // in favor of Bob
        for (int i = 0; i < 6; ++i) {
          C[i] = (rng() & 1)
            ? (((rng() & 1) ? B1 : B0) ^ (1 + rng() % 3))
            : (rng() % 52);
        }
      } else if (phase == 2) {
        // in favor of Draw
        int cnt[13] = {};
        ++cnt[A0 >> 2];
        ++cnt[A1 >> 2];
        --cnt[B0 >> 2];
        --cnt[B1 >> 2];
        C.clear();
        for (int r = 0; r < 13; ++r) {
          for (int i = abs(cnt[r]); --i >= 0; ) {
            C.push_back(r << 2 | (rng() & 3));
          }
        }
        for (; C.size() < 6; ) {
          const int r = rng() % 13;
          C.push_back(r << 2 | (rng() & 3));
          C.push_back(r << 2 | (rng() & 3));
        }
        assert((int)C.size() == 6);
      } else {
        break;
      }
      set<int> ss{A0, A1, B0, B1};
      ss.insert(C.begin(), C.end());
      if (ss.size() == 10) {
        const int res = simulate(A0, A1, B0, B1, C);
        // cerr << res << " " << C << endl;
        ans[1 + res] = C;
        if (++numTries >= NUM_TRIES) {
          break;
        }
      }
    }
  }
  /*
  for (const int z : {+1, -1, 0}) {
    if (ans[1 + z].size()) {
      printf("YES");
      for (const int c : ans[1 + z]) {
        printf(" %s", cardString(c).c_str());
      }
      puts("");
    } else {
      puts("NO");
    }
  }
  */
  return ans;
}

int other(int A, int B, int k) {
  for (int u = 1; u < 4; ++u) if ((A ^ u) != B) {
    if (!k--) return A ^ u;
  }
  assert(false);
}

vector<vector<int>> solve(int A0, int A1, int B0, int B1) {
  if ((A0>>2) > (A1>>2)) swap(A0, A1);
  if ((B0>>2) > (B1>>2)) swap(B0, B1);
// cerr<<COLOR("33")<<"[solve] "<<cardString(A0)<<" "<<cardString(A1)<<" "<<cardString(B0)<<" "<<cardString(B1)<<COLOR()<<endl;
  const int a0 = A0 >> 2, a1 = A1 >> 2;
  const int b0 = B0 >> 2, b1 = B1 >> 2;
  int fs[13] = {};
  fs[a0] |= 1 << 0;
  fs[a1] |= 1 << 1;
  fs[b0] |= 1 << 2;
  fs[b1] |= 1 << 3;
  vector<vector<int>> ans(3);
  auto &alice = ans[1 + (+1)];
  auto &bob   = ans[1 + (-1)];
  auto &draw  = ans[1 + 0   ];
  {
    set<int> used{A0, A1, B0, B1};
    for (const int r : {a1, a0}) if ((fs[r] & 3) >= (fs[r] >> 2)) {
      for (int s = 0; s < 4; ++s) {
        const int c = r << 2 | s;
        if (used.insert(c).second) {
          alice.push_back(c);
        }
      }
    }
    if (alice.size() > 3) alice.resize(3);
    for (int r = 13; --r >= 0; ) if (!(fs[r] >> 2)) {
      for (int s = 0; s < 4; ++s) {
        const int c = r << 2 | s;
        if (used.insert(c).second) {
          alice.push_back(c);
          break;
        }
      }
    }
    assert(alice.size() >= 6);
    alice.resize(6);
  }
  if (a0 == a1) {
    if (b0 == b1) {
      ///////////////////////////////////////////////////// a0 == a1 && b0 == b1
      if (b0 < a0) {
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            bob = {other(B0,B1,0), other(B0,B1,1), r0<<2|0, r0<<2|1, r1<<2|2, r1<<2|3};
            break;
          }
          break;
        }
      } else if (b0 == a0) {
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            for (int r2 = r1 + 1; r2 < 13; ++r2) if (!fs[r2]) {
              draw = {r0<<2|0, r0<<2|1, r1<<2|0, r1<<2|1, r2<<2|2, r2<<2|3};
              break;
            }
            break;
          }
          break;
        }
      } else if (a0 < b0) {
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            bob = {other(B0,B1,0), other(B0,B1,1), r0<<2|0, r0<<2|1, r1<<2|2, r1<<2|3};
            break;
          }
          break;
        }
      } else {
        assert(false);
      }
    } else {
      ///////////////////////////////////////////////////// a0 == a1 && b0 != b1
      if (a0 < b0) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
      } else if (a0 == b0) {
        // ALICE
        for (int r0 = 13; --r0 >= 0; ) if (!fs[r0]) {
          for (int r1 = r0; --r1 >= 0; ) if (!fs[r1]) {
            alice = {A0^A1^B0, B1^1, r0<<2|0, r0<<2|1, r1<<2|2, r1<<2|3};
            break;
          }
          break;
        }
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            for (int r2 = r1 + 1; r2 < 13; ++r2) if (!fs[r2]) {
              bob = {B1^1, B1^2, r0<<2|0, r0<<2|1, r1<<2|2, r2<<2|3};
              break;
            }
            break;
          }
          break;
        }
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          draw = {A0^A1^B0, B1^1, B1^2, B1^3, r<<2|0, r<<2|1};
          break;
        }
      } else if (b0 < a0 && a0 < b1) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
      } else if (a0 == b1) {
        if (a0 != 12) {
          bob = {B0^1, B0^2, B0^3, 12<<2|0, 12<<2|1, 12<<2|2};
        } else if ((B0 & 3) == (B1 & 3)) {
          // FLUSH
          for (int r = 0; r < 13; ++r) if (!fs[r]) {
            bob.push_back(r << 2 | (B0 & 3));
            if (bob.size() == 6) break;
          }
        } else if (8 <= b0 && b0 <= 11) {
          // STRAIGHT
          for (int r = 8; r <= 11; ++r) if (b0 != r) {
            bob.push_back(r << 2 | 0);
            bob.push_back(r << 2 | 1);
          }
        } else if (0 <= b0 && b0 <= 3) {
          // STRAIGHT
          for (int r = 0; r <= 3; ++r) if (b0 != r) {
            bob.push_back(r << 2 | 0);
            bob.push_back(r << 2 | 1);
          }
        }
      } else if (b1 < a0) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
      } else {
        assert(false);
      }
    }
  } else {
    if (b0 == b1) {
      ///////////////////////////////////////////////////// a0 != a1 && b0 == b1
      if (b0 < a0) {
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          bob = {A0^1, A1^1, other(B0,B1,0), other(B0,B1,1), r<<2|0, r<<2|1};
          break;
        }
      } else if (b0 == a0) {
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            bob = {A0^B0^B1, r0<<2|0, r0<<2|1, r0<<2|2, r1<<2|2, r1<<2|3};
            break;
          }
          break;
        }
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            draw = {A0^B0^B1, A1^1, r0<<2|0, r0<<2|1, r1<<2|2, r1<<2|3};
            break;
          }
          break;
        }
      } else if (a0 < b0 && b0 < a1) {
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          bob = {A0^1, A1^1, other(B0,B1,0), other(B0,B1,1), r<<2|0, r<<2|1};
          break;
        }
      } else if (b0 == a1) {
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            bob = {A1^B0^B1, r0<<2|0, r0<<2|1, r0<<2|2, r1<<2|2, r1<<2|3};
            break;
          }
          break;
        }
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          draw = {A0^1, A0^2, A0^3, A1^B0^B1, r<<2|0, r<<2|1};
          break;
        }
      } else if (a1 < b0) {
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          bob = {A0^1, A1^1, other(B0,B1,0), other(B0,B1,1), r<<2|0, r<<2|1};
          break;
        }
      } else {
        assert(false);
      }
    } else {
      ///////////////////////////////////////////////////// a0 != a1 && b0 != b1
      if (a0 == b0 && a1 == b1) {
        if ((B0 & 3) == (B1 & 3)) {
          // FLUSH
          for (int r = 0; r < 13; ++r) if (!fs[r]) {
            bob.push_back(r << 2 | (B0 & 3));
            if (bob.size() == 6) break;
          }
        }
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            for (int r2 = r1 + 1; r2 < 13; ++r2) if (!fs[r2]) {
              draw = {r0<<2|0, r0<<2|1, r1<<2|0, r1<<2|1, r2<<2|2, r2<<2|3};
              break;
            }
            break;
          }
          break;
        }
      } else if (a0 == b0) {
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = r0 + 1; r1 < 13; ++r1) if (!fs[r1]) {
            bob = {other(A0,B0,0), B1^1, B1^2, B1^3, r0<<2|0, r1<<2|1};
            break;
          }
          break;
        }
        draw = {other(A0,B0,0), other(A0,B0,1), A1^1, B1^1, B1^2, B1^3};
      } else if (a0 == b1) {
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          bob = {B0^1, B0^2, B0^3, r<<2|0, r<<2|1, r<<2|2};
          break;
        }
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          draw = {A1^1, B0^1, B0^2, B0^3, r<<2|0, r<<2|1};
          break;
        }
      } else if (a1 == b0) {
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          bob = {B1^1, B1^2, B1^3, r<<2|0, r<<2|1, r<<2|2};
          break;
        }
        for (int r0 = 0; r0 < 13; ++r0) if (!fs[r0]) {
          for (int r1 = 13; --r1 > r0; ) if (!fs[r1]) {
            draw = {A0^1, B1^1, r0<<2|0, r0<<2|1, r1<<2|2, r1<<2|3};
            break;
          }
          break;
        }
      } else if (a1 == b1) {
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          bob = {B0^1, B0^2, B0^3, r<<2|0, r<<2|1, r<<2|2};
          break;
        }
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          draw = {A0^1, B0^1, B0^2, B0^3, r<<2|0, r<<2|1};
          break;
        }
      } else if (a0 < a1 && a1 < b0 && b0 < b1) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
      } else if (a0 < b0 && b0 < a1 && a1 < b1) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
        for (int r = 0; r < 13; ++r) if (!fs[r]) {
          draw = {A0^1, A1^1, B0^1, B1^1, r<<2|0, r<<2|1};
          break;
        }
      } else if (a0 < b0 && b0 < b1 && b1 < a1) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
        draw = {A0^1, A1^1, B0^1, B1^1, B1^2, B1^3};
      } else if (b0 < a0 && a0 < a1 && a1 < b1) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
      } else if (b0 < a0 && a0 < b1 && b1 < a1) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
        draw = {A0^1, A1^1, B0^1, B0^2, B0^3, B1^1};
      } else if (b0 < b1 && b1 < a0 && a0 < a1) {
        bob = {B0^1, B0^2, B0^3, B1^1, B1^2, B1^3};
      } else {
        assert(false);
      }
    }
  }
  return ans;
}

void stress() {
  mt19937_64 rng(233);
  for (int iter = 1; ; ++iter) {
    int A0, A1, B0, B1;
    for (; ; ) {
      A0 = rng() % 52;
      A1 = (rng() & 1) ? (A0 ^ (1 + rng() % 3)) : (rng() % 52);
      B0 = rng() % 52;
      B1 = (rng() & 1) ? (B0 ^ (1 + rng() % 3)) : (rng() % 52);
      if (set<int>{A0, A1, B0, B1}.size() == 4) {
        break;
      }
    }
    const string input = cardString(A0) + " " + cardString(A1) + " " + cardString(B0) + " " + cardString(B1);
    const auto brt = brute(A0, A1, B0, B1);
    const auto slv = solve(A0, A1, B0, B1);
    
    for (const int z : {+1, -1, 0}) {
      const auto &C = slv[1 + z];
      if (C.size()) {
        assert(C.size() == 6);
        for (int i = 0; i < 6; ++i) {
          assert(0 <= C[i]); assert(C[i] < 52);
        }
        set<int> ss{A0, A1, B0, B1};
        ss.insert(C.begin(), C.end());
        assert(ss.size() == 10);
        const int res = simulate(A0, A1, B0, B1, C);
        if (res != z) {
          cerr << "FAIL " << iter << " " << z << " " << input << " " << tos(brt[1 + z]) << " " << tos(C) << ": " << res << endl;
        }
        assert(res == z);
        if (!brt[1 + z].size()) {
          cerr << "WAO " << iter << " " << z << " " << input << " " << tos(brt[1 + z]) << " " << tos(C) << endl;
        }
      } else {
        if (brt[1 + z].size()) {
          cerr << "FAIL " << iter << " " << z << " " << input << " " << tos(brt[1 + z]) << " " << tos(C) << endl;
        }
        assert(!brt[1 + z].size());
      }
    }
    
    if (!(iter & (iter - 1))) {
      cerr << "PASSED iter = " << iter << endl;
    }
  }
}

int main() {
#ifdef LOCAL
  stress();
#endif
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    const int A0 = readCard();
    const int A1 = readCard();
    const int B0 = readCard();
    const int B1 = readCard();
    
    const auto ans = solve(A0, A1, B0, B1);
    for (const int z : {+1, -1, 0}) {
      if (ans[1 + z].size()) {
        printf("YES");
        for (const int c : ans[1 + z]) {
          printf(" %s", cardString(c).c_str());
        }
        puts("");
      } else {
        puts("NO");
      }
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3676kb

input:

3
JC 4H
TS 5D
7C 3C
7H TH
2D KH
4D JC

output:

YES JD JH JS AC KC QC
YES 5C 5S 5H TH TD TC
YES 4S JD 5C TH TD TC
YES 7D 7S 3D AC KC QC
YES TS TC TD 2C 2D 2H
YES 3D TS 2C 2D AH AS
YES KC KD KS AC QC TC
YES 4C 4S 4H JD JH JS
YES 2C KS 4C JD JH JS

result:

ok 3 test cases (3 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

2
AS AH
AC AD
AS AH
2S 2H

output:

YES KC QC JC TC 9C 8C
NO
YES 2C 2D 3C 3D 4H 4S
YES AC AD KC QC JC TC
YES 2D 2C 3C 3D 4H 4S
NO

result:

ok 2 test cases (2 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

1
3C 3D
3H 5S

output:

YES 3S 5H AC AD KH KS
YES 5H 5D 2C 2D 4H 6S
YES 3S 5H 5D 5C 2C 2D

result:

ok 1 test cases (1 test case)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

1
9C KC
JC 5D

output:

YES KD KH KS AC QC TC
YES 5C 5S 5H JD JH JS
YES 9D KD 5C 5S 5H JD

result:

ok 1 test cases (1 test case)

Test #5:

score: 0
Accepted
time: 227ms
memory: 3796kb

input:

100000
6S 7C
KH 3S
5S 2D
AC TS
QD 6H
TC JD
5C AD
4S TH
AD 3S
JC 5S
TH QH
9S JH
AD JC
JS 7H
3S 9S
JC 6S
4D 7S
3S JH
AD JS
7D 4D
7D QS
QH JC
4H JS
7H TS
5D AD
3S 8D
AC TH
5D 3S
9H TD
TS 7D
7D 8C
AD 5H
7C QS
2C TH
QD AS
4S 2H
8D JS
9S 5H
2C TC
2D 5S
TD 2C
AS 2D
6H 6S
AC 2S
2C 8D
4C KS
JD 9D
2D AD
AS QH...

output:

YES 7D 7H 7S AC QC JC
YES 3H 3D 3C KS KC KD
NO
YES 5C 5D 5H KC QC JC
YES TH TD TC AD AH AS
NO
YES QC QH QS AC KC 9C
YES TD TH TS JC JS JH
YES 6S QC TD JC JS JH
YES AC AH AS KC QC JC
YES 4H 4D 4C TS TC TD
YES 5D AC 4H 4D 4C TS
YES AC AH AS KC QC TC
YES 5H 5D 5C JD JH JS
YES 3H AC 5H JD JH JS
YES QC Q...

result:

ok 100000 test cases (100000 test cases)

Test #6:

score: 0
Accepted
time: 229ms
memory: 3720kb

input:

100000
6D 7D
8C JH
2C 4S
3D 2D
8C AD
7H 5S
QC JC
JH 7H
TC TH
9D 5D
7S 3C
TC 7D
JD 5C
4C 6D
4S 5H
7D 6C
AC TH
7D 4D
QH 3D
TS KC
AD 8D
5H 3S
9D 6D
6S 2C
JH KS
7C 3H
QD 7C
7S KD
8H 9D
3C KD
7H 9S
KD TS
5D KH
3C AC
4S 3D
4C 3C
9C 2H
8C JH
8H 9C
KS 5S
QC 4S
9H TH
TD KD
JC 8D
AS KH
KS 2H
7D 6D
AD 6S
7H 6C...

output:

YES 7C 7H 7S AC KC QC
YES 8D 8H 8S JS JC JD
NO
YES 4C 4D 4H AC KC QC
YES 2H 3C 3S 3H 5C 6D
YES 2H 2S 4H 3C 3S 3H
YES AC AH AS KC QC JC
YES 5H 5D 5C 7S 7C 7D
NO
YES QD QH QS AC KC TC
YES 7S 7C 7D 2C 2D 2H
YES QD 7S 7C 7D 2C 2D
YES TD TS AC KC QC JC
YES 5C 5S 5H 9C 9S 9H
NO
YES 7C 7H 3D AC KC QC
YES T...

result:

ok 100000 test cases (100000 test cases)

Test #7:

score: 0
Accepted
time: 225ms
memory: 3680kb

input:

100000
5S 6H
6D KH
AS 3D
KS 3S
7S 4S
7D JD
4D 6D
7D AD
2C JH
6C QD
7H TC
JD 3C
TC 2C
AH JH
3C 9S
5S 9H
JC 6H
QS 3H
6D 7C
2D 4D
9H 8C
QC KS
7H 9S
TH JS
JS AS
8H QH
8D 5S
7S 3S
2D QD
AC 9H
3H 6S
8H JC
3H 8C
4H AS
QC TH
9S 6S
3S 9D
7C TC
QS JC
6S 9S
4C 9S
5S 6D
3H AH
4D 3D
7H 2C
QH 7C
3C QS
QD KH
5C QH...

output:

YES 6C 6S 5C AC QC JC
YES KS KC KD 2C 2D 2H
YES 5H KS 2C 2D AH AS
YES AC AD AH QC JC TC
YES 3C KH KD KC 2C 4D
YES 3C 3H AH KH KD KC
YES 7C 7H 4C AC KC QC
YES JC JS JH 2C 2D 2H
YES 4H JC 2C 2D AH AS
YES 6C 6H 6S KC QC JC
YES 7C 7S 7H AC AS AH
NO
YES JC JD JS AC KC TC
YES 6D 6H 6S QC QS QH
YES 2D JS 6...

result:

ok 100000 test cases (100000 test cases)

Test #8:

score: 0
Accepted
time: 216ms
memory: 3716kb

input:

100000
QS 2C
8D 3H
AD JD
5H 9H
5C JS
4S 3C
9D 9S
TH QC
6C 6H
QH 4S
JH JD
7H 6C
KC 9D
4C 5C
3H QC
6H 8H
7S 4S
3S 8C
6C 4D
AD 9H
8H 3S
JS KC
3C AS
9S 2C
8D 7D
8S KC
4S JD
TH 7D
3D 9S
AD AC
9D 2D
2S KH
6D AC
7H 2D
4D AC
5D JC
JH JD
2C 6D
8S 6D
9S 5S
JD 9C
6C 7S
TC 6H
TH 9H
JD 8D
8H KH
5C 9C
AH 9D
2S TH...

output:

YES QC QD QH AC KC JC
YES 3S 3C 3D 8C 8S 8H
YES 2D QH 3S 8C 8S 8H
YES AC AH AS KC QC TC
YES 5S 5C 5D 9S 9C 9D
NO
YES JC JD JH AC KC QC
YES 3D 3H 3S 4H 4D 4C
NO
YES 9C 9H AC KC JC 8C
YES TS TC TD QD QH QS
NO
YES 6D 6S AC KC JC TC
YES 4H 4D 4C QS QC QD
NO
YES JC JS AC KC QC TC
YES 6D 6H 6S 7S 7C 7D
NO...

result:

ok 100000 test cases (100000 test cases)

Test #9:

score: 0
Accepted
time: 227ms
memory: 3956kb

input:

100000
JS TS
6S AH
9H 2D
9D 2C
8S TH
KC 9H
AD 7H
AS 2S
6D TC
TS 9D
2S 3C
JH 2D
7D QH
2D KC
JD 8C
4D TS
7C 2H
JC 6C
2S 8C
AH 5C
JS 2D
AH QD
6D 6H
9D TH
KD 2H
2S AC
2H 3D
AH 9H
2H KC
TS JC
2H 5H
8S KD
4H 6C
5S QS
3D AC
5S JC
7S 9C
KS 5S
9C AD
KC 4H
5H KH
TD KD
8C 4D
3S 8S
5D JC
JS KS
8H AD
8D 2H
AS QD...

output:

YES JC JD JH KC QC 9C
YES 6H 6D 6C AS AC AD
NO
YES 9C 9S 2H AC KC QC
NO
YES 3C 3D 4C 4D 5H 5S
YES TC TD TS AC QC JC
YES 9S 9C 9D KD KH KS
YES 8H TS 9S KD 2C 2D
YES AC AH 7C KC QC JC
YES 2H 2D 2C 3C 3D 3H
YES 7S 2H 2D 2C 3C 3D
YES TD TH 6C AC KC QC
YES 9C 9S 9H 2C 2D 2H
YES 6C 9C 9S 9H 2C 2D
YES 3D 3...

result:

ok 100000 test cases (100000 test cases)

Test #10:

score: 0
Accepted
time: 231ms
memory: 3956kb

input:

100000
TH 9C
3H KH
QD 5C
AS 7D
6D 4C
5S 7H
2D 6H
9C 4C
JD AC
7D JC
TC 3S
QH 2D
JC 5H
9D 7S
6S TC
7S KC
4S TS
7S QS
TD KS
7D 8H
KS 2D
5H 7C
9C KH
2S 9D
JD 5H
9C QH
7D QC
6H KC
6S 7D
KS 6C
TC KD
2C 4D
3S 5S
AD 6S
KH 7D
KS 5H
QC QH
8C 3S
KH AC
8D TS
QD TH
9C 8C
KS 8H
9C QC
6D 8H
9D TH
9C 5S
6C 6S
KH 6S...

output:

YES TC TD TS AC QC JC
YES 3S 3C 3D KS KC KD
NO
YES QC QH QS KC JC TC
YES 7C 7S 7H AH AD AC
YES 5D QC 7C AH 2C 2D
YES 6C 6H 6S AC KC QC
YES 5H 5D 5C 7S 7C 7D
YES 4D 6C 5H 7S 2C 2D
YES 6C 6D 6S AC KC QC
YES 4D 4H 4S 9D 9H 9S
YES 2C 6S 4D 9D 3C 3D
YES AD AH AS KC QC TC
YES 7C 7S 7H 2C 2D 2H
YES AD 7C 7...

result:

ok 100000 test cases (100000 test cases)