QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107265#5444. Tavern Chesswarner1129#WA 7ms3716kbC++202.6kb2023-05-20 17:44:062023-05-20 17:44:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 17:44:07]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3716kb
  • [2023-05-20 17:44:06]
  • 提交

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'