QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297428 | #4859. Poker Game: Construction | ucup-team087# | WA | 3ms | 3936kb | C++14 | 8.5kb | 2024-01-04 14:04:07 | 2024-01-04 14:04:08 |
Judging History
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));
}
////////////////////////////////////////////////////////////////////////////////
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];
}
void solve(int A0, int A1, int B0, int B1) {
// cerr<<COLOR("33")<<"[solve] "<<cardString(A0)<<" "<<cardString(A1)<<" "<<cardString(B0)<<" "<<cardString(B1)<<COLOR()<<endl;
constexpr int NUM_ITERS = 1 << 9;
vector<int> ans[3];
for (int phase = 0; phase < 3; ++phase) {
for (int iter = 0; iter < NUM_ITERS; ++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;
const int seed = phase * NUM_ITERS + iter;
mt19937_64 rng(seed);
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) ^ (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;
}
}
}
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");
}
}
}
int main() {
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();
solve(A0, A1, B0, B1);
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3936kb
input:
3 JC 4H TS 5D 7C 3C 7H TH 2D KH 4D JC
output:
YES 4S 5S TH JD QD QH YES 9H 6S AD 6H 2C TH YES 4S 5H TH JS TC TD YES JD 4C 8H AC 8S 2D YES AS AD 4D 6D KC TC YES 3D TS 2C 2H AS AD YES 2H 4H JD KC 8D 8H YES JS 4C 6D 7C 7D 9H YES 2S 4S JS KC JD JH
result:
ok 3 test cases (3 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 3652kb
input:
2 AS AH AC AD AS AH 2S 2H
output:
YES TS 7D KC 4D 4C 7C NO YES 8D 8H TH TS 5H 5C YES 2D 2C AD AC 5H 5C YES 3D JD 2D 4C 2C 8H NO
result:
ok 2 test cases (2 test cases)
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 3776kb
input:
1 3C 3D 3H 5S
output:
YES 3S 5C 4D 4C KD KC YES 5C KS 5H 8H 2S JC NO
result:
wrong answer Jury find answer but partcitant not. (test case 1)