QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #118435 | #4858. Poker Game: Decision | Antonn_114 | TL | 4ms | 3516kb | C++17 | 6.4kb | 2023-07-03 15:44:06 | 2023-07-03 15:44:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// Write down the limits of the problem here
struct Card{
unsigned char rank, suit;
Card() {}
Card(const string& s) : rank(s[0]), suit(s[1]) {}
inline bool operator<(const Card& c){
return rank < c.rank;
}
};
const unsigned char flush_order[] = {'A', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K'};
unordered_map<unsigned char, int> rank_dict{
{'A', 13},
{'K', 12},
{'Q', 11},
{'J', 10},
{'T', 9},
{'9', 8},
{'8', 7},
{'7', 6},
{'6', 5},
{'5', 4},
{'4', 3},
{'3', 2},
{'2', 1}
};
unordered_map<unsigned char, int> flush_dict{{'A', 1}, {'2', 2}, {'3', 3}, {'4', 4}, {'5', 5}, {'6', 6}, {'7', 7}, {'8', 8}, {'9', 9}, {'T', 10}, {'J', 11}, {'Q', 12}, {'K', 13}};
pair<int, vector<unsigned char>> eval(vector<Card> &hand){
multiset<int> ranks;
set<int> ranks_s;
bool same_suit = true;
bool royal = true;
bool straight = false;
int foo = -1;
for (auto& i : hand){
if (foo == -1) foo = i.suit;
else if (foo != i.suit) same_suit = false;
ranks.insert(i.rank);
ranks_s.insert(i.rank);
if ('1' <= i.rank && i.rank <= '9') royal = false;
}
if (royal && same_suit) return {10, {'T', 'J', 'Q', 'K', 'A'}};
for (int i = 0; i < 9; i++){
bool ok = true;
for (int j = 0; j < 5; j++){
if (!ranks.count(flush_order[i + j])){
ok = false;
continue;
}
}
if (ok){
straight = true;
break;
}
}
vector<unsigned char> r2;
for (auto it = ranks.rbegin(); it != ranks.rend(); it++){
r2.push_back(*it);
}
sort(r2.begin(), r2.end(), [&](const unsigned char& lhs, const unsigned char&rhs) {
if (straight)
return flush_dict[lhs] > flush_dict[rhs];
if (ranks.count(lhs) == ranks.count(rhs)) return rank_dict[lhs] > rank_dict[rhs];
return ranks.count(lhs) > ranks.count(rhs);
});
if (same_suit && straight) return {9, r2};
if (ranks_s.size() == 2 && (ranks.count(*ranks_s.begin()) == 1 || ranks.count(*ranks_s.begin()) == 4)) return {8, r2};
if (ranks_s.size() == 2) return {7, r2};
if (ranks_s.size() == 5 && same_suit) return {6, r2};
if (straight || royal) return {5, r2};
if (ranks_s.size() == 3 && (ranks.count(*ranks_s.begin()) == 3 ||
(ranks.count(*ranks_s.begin()) == 1 && ranks.count(*next(ranks_s.begin())) == 3) ||
(ranks.count(*ranks_s.begin()) == 1 && ranks.count(*next(ranks_s.begin())) == 1))) return {4, r2};
if (ranks_s.size() == 3) return {3, r2};
if (ranks_s.size() == 4) return {2, r2};
return {1, r2};
}
vector<Card> Alice, Bob, Common;
int dp[128][128];
void backtrack(int i, int bm1, int bm2){
if (dp[bm1][bm2] != -2){
return;
}
if (i == 3){
vector<Card> left;
for (int ii = 0; ii < 6; ii++){
if ((bm1 >> ii) & 1) continue;
if ((bm2 >> ii) & 1) continue;
left.push_back(Common[ii]);
}
int win_a = 0, win_b = 0, draw = 0;
for (int ii = 0; ii < left.size(); ii++){
Alice.push_back(left[ii]);
for (int jj = 0; jj < left.size(); jj++){
if (ii == jj) continue;
Bob.push_back(left[jj]);
}
auto score_a = eval(Alice);
auto score_b = eval(Bob);
if (score_a.first > score_b.first) win_a++;
else if (score_b.first > score_a.first) win_b++;
else{
bool ok = false;
for (int jj = 0; jj < 5; jj++){
if (score_a.second[jj]!= score_b.second[jj]){
if (rank_dict[score_a.second[jj]] > rank_dict[score_b.second[jj]])
win_a++;
else
win_b++;
ok = true;
break;
}
}
if (!ok) draw++;
}
Alice.pop_back();
Bob.pop_back();
Bob.pop_back();
}
if (win_a >= 2) dp[bm1][bm2] = 1;
else if (draw >= 2) dp[bm1][bm2] = 0;
else if (win_b >= 2) dp[bm1][bm2] = -1;
else dp[bm1][bm2] = 0;
return;
}
int win_a = 0, win_b = 0, draw = 0;
for (int ii = 0; ii < 6; ii++){
if ((bm1 >> ii)&1) continue;
if ((bm2 >> ii)&1) continue;
if (i & 1) Bob.push_back(Common[ii]), bm1 ^= (1<<ii);
else Alice.push_back(Common[ii]), bm2 ^= (1<<ii);
backtrack(i + 1, bm1, bm2);
if (dp[bm1][bm2] == 1) win_a++;
if (dp[bm1][bm2] == 0) draw++;
if (dp[bm1][bm2] == -1) win_b++;
if (i&1) Bob.pop_back(), bm1 ^= (1<<ii);
else Alice.pop_back(), bm2 ^= (1 <<ii);
}
if (i & 1){
if (win_b)dp[bm1][bm2] = -1;
else if (draw) dp[bm1][bm2] = 0;
else dp[bm1][bm2] = 1;
}else{
if (win_a) dp[bm1][bm2] = 1;
else if (draw) dp[bm1][bm2] = 0;
else dp[bm1][bm2] = -1;
}
return;
}
int main() {
// Try to avoid cin, cout :)
int tc = 1; cin >> tc;
while(tc--) {
/// Your solution here
string s;
for (int i = 0; i < 128; i++) for (int j = 0; j < 128; j++) dp[i][j] = -2;
Alice.clear();
Bob.clear();
Common.clear();
for (int i = 0; i < 2; i++){
cin >> s; Alice.push_back(Card(s));
}
for (int i =0;i < 2; i++){
cin >> s; Bob.push_back(Card(s));
}
for (int i= 0; i < 6; i++){
cin >> s; Common.push_back(Card(s));
}
backtrack(0, 0, 0);
if (dp[0][0] == 1) cout << "Alice\n";
else if (dp[0][0] == 0) cout << "Draw\n";
else cout << "Bob\n";
}
return 0;
}
/*
* Ermm don't underestimate Div2A, pls...
*
* IMPORTANT:: If there isn't a clear-cut approach for your program, DO NOT CODE YET!
*
* Analyze the time complexity and space complexity even if it *seems* efficient
*
* Write down some notes for more complicated problems
*
* Also, please, CP isn't supposed to be complicated
*
**/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 3452kb
input:
9 JC 4H TS 5D JS JH JD 4S 4C 4D JC 4H TS 5D TH TC TD 5S 5H 5C JC 4H TS 5D 4S JS 5S TH TC TD 7C 3C 7H TH 3S 3H 3D 2C 4H 5S 7C 3C 7H TH 2H 4H 5H 6H 8H 9H 7C 3C 7H TH TS 3S 2S 2H 4C 4D 2D KH 4D JC 2S 2H 2C KS KC KD 2D KH 4D JC 4S 4H 4C JS JH JD 2D KH 4D JC 2S KS 4S JS JH JD
output:
Alice Bob Draw Alice Bob Draw Alice Bob Draw
result:
ok 9 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
1 AS 2H 2S 6H 3S 3H 4S 4H 5S 5H
output:
Bob
result:
ok single line: 'Bob'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
1 5D 9H KC 6H 9C QH JH 3C AC 9S
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: -100
Time Limit Exceeded
input:
100000 5C JS KS 7S 4D 2D KH 6S 6D 6H 2C KS 7D 5D 5S AH 3S 9C JH 5H 9D 4D 3H TS 2D 2C 7H 3D AH 3S KS 8H 7H QD TH 4H QS 8S 6D TD JS 8D 4H 2S AH 2H 2C 6S 4C 8S JS KD 4S 2D JH 4C 6S QD AH 7C 9D 4H QH JS KH QC 6S 5D JC AD KD 5D 4C TC 4H 2C TD 7S 6S QH 3C 5C QC 9D QH 5D AC 7D 8C 8S 4S 6H 9C 8C JC 7S QH 6C...
output:
Bob Bob Bob Alice Bob Alice Bob Bob Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Bob Bob Alice Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Bob Bob Alice Alice Bob Bob Bob Alice Alice Alice Bob Bob Alice Alice Alice Alice Alice Alice Al...