QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107265 | #5444. Tavern Chess | warner1129# | WA | 7ms | 3716kb | C++20 | 2.6kb | 2023-05-20 17:44:06 | 2023-05-20 17:44:07 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); }
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; }
#define debug(args...) (dbg("(" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "[" + string(#args) + ") = ", org(args))
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
template<class T> bool chmin(T &a, T b) { return b < a and (a = b, true); }
template<class T> bool chmax(T &a, T b) { return b > a and (a = b, true); }
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define ff first
#define ss second
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;
template<class T>
using BST = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr int INF = 1<<30;
constexpr long long mod = 998244353;
void solve() {
int n, m;
cin >> n >> m;
using data = vector<array<int, 3>>;
data A(n), B(m);
for (auto &[a, b, c] : A) cin >> a, b = a, c = 0;
for (auto &[a, b, c] : B) cin >> a, b = a, c = 0;
array<double, 3> cnt{};
function<void(data, data, int, double)> dfs = [&](data A, data B, int f, double p) -> void {
if (A.empty() and B.empty()) return void(cnt[2] += p);
if (B.empty()) return void(cnt[0 ^ f] += p);
if (A.empty()) return void(cnt[1 ^ f] += p);
int s = 0;
for (int i = 0; i < A.size(); i++) if (A[i][2] < A[s][2]) s = i;
A[s][2]++;
double ch = B.size();
for (int i = 0; i < B.size(); i++) {
debug(s, i);
auto ta = A, tb = B;
ta[s][0] -= tb[i][1];
tb[i][0] -= ta[s][1];
//ta[p][1] = ta[p][0], tb[i][1] = tb[i][0];
//tb[i][2]++;
if (ta[s][0] <= 0) ta.erase(begin(ta) + s);
if (tb[i][0] <= 0) tb.erase(begin(tb) + i);
dfs(tb, ta, f ^ 1, p / ch);
}
};
double p = (A.size() == B.size()) ? 0.5 : 1;
if (A.size() >= B.size()) dfs(A, B, 0, p);
if (B.size() >= A.size()) dfs(B, A, 1, p);
double tot = cnt[0] + cnt[1] + cnt[2];
debug(tot);
orange(all(cnt));
for (double x : cnt)
cout << x << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}
/*
2 3
2 5
3 4 1
6 6
1 1 4 5 1 4
1 1 4 5 1 4
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
input:
2 3 2 5 3 4 1
output:
0.125 0.75 0.125
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 3716kb
input:
6 6 1 1 4 5 1 4 1 1 4 5 1 4
output:
0.241867 0.241867 0.516265
result:
wrong answer 1st numbers differ - expected: '0.2418673', found: '0.2418670', error = '0.0000003'