QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#590558 | #8063. Seven Up | nickbelov# | AC ✓ | 1610ms | 125396kb | C++20 | 2.9kb | 2024-09-26 04:57:05 | 2024-09-26 04:57:05 |
Judging History
answer
#include <vector>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
constexpr int N = 8;
using DECK = array<int,N+1>; //14th one is a bitmask, :holyfuck:
map<DECK,ld> dp;
string s;
char mp[256];
ld rec(DECK d){
if(d.back()==0) return 0;
if(dp.contains(d)) return dp[d];
int sm = accumulate(d.begin(),d.end()-1,0);
// ranges::copy(d,oit<int>()),cout<<endl;
ld &state = dp[d];
for(int i=0;i<N;i++){
if(!d[i]) continue;
ld p = d[i]/((ld)sm);
d[i]--;
int old_mask = d.back(),cur=i;
while(cur<7 and d.back()&(1<<cur)){
d.back()^=(1<<cur);
cur=mp[s[cur]];
}
state += p*(rec(d)+1);
d[i]++;
d.back()=old_mask;
}
return state;
}
void run()
{
cin >> s;
DECK d{0};
d.back() = (1<<7)-1;
for(int i : rep(7)){
d[i]=4;
}
d[7] = 52 - 4*7;
for(char c : s){
int idx = mp[c];
if(idx<7) d[idx]--;
else d[7]--;
}
auto ans = rec(d);
cout << fixed << setprecision(10) << ans << '\n';
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
string cards{"A23456789TJQK"};
for(int i : rep(len(cards))) mp[cards[i]]=i;
run();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 614ms
memory: 53820kb
input:
A9Q22T5
output:
19.8812971342
result:
ok found '19.8812971', expected '19.8812971', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1610ms
memory: 125396kb
input:
JQQQKKK
output:
20.9131450564
result:
ok found '20.9131451', expected '20.9131451', error '0.0000000'
Test #3:
score: 0
Accepted
time: 456ms
memory: 42560kb
input:
A234567
output:
25.1723868237
result:
ok found '25.1723868', expected '25.1723868', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
234567A
output:
2.0909090909
result:
ok found '2.0909091', expected '2.0909091', error '0.0000000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 4784kb
input:
2356A74
output:
6.0475524476
result:
ok found '6.0475524', expected '6.0475524', error '0.0000000'
Test #6:
score: 0
Accepted
time: 182ms
memory: 20952kb
input:
2A43657
output:
15.7540446396
result:
ok found '15.7540446', expected '15.7540446', error '0.0000000'
Test #7:
score: 0
Accepted
time: 105ms
memory: 15284kb
input:
AAAA222
output:
18.9345686993
result:
ok found '18.9345687', expected '18.9345687', error '0.0000000'
Test #8:
score: 0
Accepted
time: 143ms
memory: 18108kb
input:
274AA25
output:
13.2888888889
result:
ok found '13.2888889', expected '13.2888889', error '0.0000000'
Test #9:
score: 0
Accepted
time: 594ms
memory: 54064kb
input:
7K7A598
output:
19.8812971342
result:
ok found '19.8812971', expected '19.8812971', error '0.0000000'
Test #10:
score: 0
Accepted
time: 427ms
memory: 41612kb
input:
7K586T4
output:
15.8051282051
result:
ok found '15.8051282', expected '15.8051282', error '0.0000000'
Test #11:
score: 0
Accepted
time: 491ms
memory: 46660kb
input:
9353K2T
output:
17.5812971342
result:
ok found '17.5812971', expected '17.5812971', error '0.0000000'
Test #12:
score: 0
Accepted
time: 923ms
memory: 77580kb
input:
K59QKT3
output:
18.9345686993
result:
ok found '18.9345687', expected '18.9345687', error '0.0000000'
Test #13:
score: 0
Accepted
time: 624ms
memory: 53816kb
input:
52Q2J68
output:
19.8812971342
result:
ok found '19.8812971', expected '19.8812971', error '0.0000000'