QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#297434 | #4859. Poker Game: Construction | ucup-team087# | TL | 1ms | 3792kb | C++14 | 8.6kb | 2024-01-04 14:08:06 | 2024-01-04 14:08:06 |
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_TRIES = 20;
mt19937_64 rng(58);
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) ^ (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");
}
}
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3740kb
input:
3 JC 4H TS 5D 7C 3C 7H TH 2D KH 4D JC
output:
YES 4S 5C TC JS 6S 6D YES 4C 5C 5S QH TC TD YES 4S 5S TH JS 5H 5C YES 2S 6H 6D KD 8D 6S YES 4C TS TC QH 7D TD YES 3S TD KC KD QS QD YES 2H 4S JH KC 3C 3H YES AC 5S 4S 4H 5D 7C YES 2H 4S JS KC JD JH
result:
ok 3 test cases (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 AS AH AC AD AS AH 2S 2H
output:
YES 2C QH 4H 4C 6C TS NO YES 4H 4C 6C 6S 2H 2S YES 2D 2C AC AD TC TH YES QH 2C 5H KC JH 2D NO
result:
ok 2 test cases (2 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
1 3C 3D 3H 5S
output:
YES 3S 5C AC AH 4C 4H YES 7C 7H 9S 5D 5C JD YES 3S 5H 5D 5C 8S 8H
result:
ok 1 test cases (1 test case)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
1 9C KC JC 5D
output:
YES 2S 6H 6D KD 8D 6S YES 4C 5C 5S QH JS TD YES 5S 9S JH KS 5H 5C
result:
ok 1 test cases (1 test case)
Test #5:
score: -100
Time Limit Exceeded
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 3H 6H 7S KC 5D 5S YES TH 9S 8H JS AH AC NO YES 2S 5D TD AS 5C 5H YES 2H 5H TC AH 6S 6D NO YES 6D TH JH QS 2D 2H YES 9S JS AC 5S TH TS NO YES 4H 5D TD AH 7C 7S YES 4C 9H 9S TS TD 5S NO YES 3H 5D JH AH 9S 9C YES 7C 7H 9S 5D 5C JD NO YES 9H TS JC QD AC AH YES 7H KH JC 9C AC 5S NO YES 7C AS TH TS 2H...