QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117552#5444. Tavern ChessUrgantTeam#WA 2ms3748kbC++233.2kb2023-07-01 17:06:042023-07-01 17:06: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-07-01 17:06:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3748kb
  • [2023-07-01 17:06:04]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <array>
#include <iomanip>
#include <unordered_map>

#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long double ld;
typedef long long ll;

const int U = 7;
using ld = long double;
using pii = pair<int, int>;
using sta = array<pii, U>;
using ai = array<int, U>;
using pdd = pair<ld, ld>;

struct state {
	sta A, B;
	int aA, aB;
	bool f;
	int finish() const {
		if (A[0].y == 0)
			if (B[0].y == 0)
				return 0;
			else
				return f ? -1 : 1;
		else
			if (B[0].y == 0)
				return f ? 1 : -1;
			else
				return 2;
	}
	ll find_hash() const {
		const ll R = 2343654461, P = 33663379, C = 1000000001;
		ll ans = R;

		ans *= P;
		ans += f;

		for (int i = 0; i < U; ++i) {
			if (A[i].y <= 0) break;
			ans *= P;
			ans += A[i].x;
			ans *= P;
			ans += A[i].y;
		}

		ans *= P;
		ans += aA;

		ans *= P;
		ans += C;

		for (int i = 0; i < U; ++i) {
			if (B[i].y <= 0) break;
			ans *= P;
			ans += B[i].x;
			ans *= P;
			ans += B[i].y;
		}

		ans *= P;
		ans += aB;

		return ans;
	}
	void kill_minion(int m, bool who) {
		if (who) {
			A[m].y = 0;
			for (int i = m; i < U - 1; ++i)
				swap(A[i], A[i + 1]);
			if (aA > m)
				--aA;
			if (A[aA].y <= 0)
				aA = 0;
		} else {
			B[m].y = 0;
			for (int i = m; i < U - 1; ++i)
				swap(B[i], B[i + 1]);
			if (aB > m)
				--aB;
			if (B[aB].y <= 0)
				aB = 0;
		}
	}
	void maybe_kill_minion(int i, bool who) {
		int health = who ? A[i].y : B[i].y;
		if (health <= 0)
			kill_minion(i, who);
	}
	void mv(int fb) {
		A[aA].y -= B[fb].x;
		B[fb].y -= A[aA].x;
		int aaa = aA++;
		maybe_kill_minion(aaa, true);
		maybe_kill_minion(fb, false);

		swap(A, B);
		swap(aA, aB);
		f = !f;
	}
};

pdd find_ans(const state& s) {
	{
		int f = s.finish();
		if (f != 2) return { f == 1, f == -1 };
	}
	static unordered_map<ll, pdd> stored;
	{
		auto it = stored.find(s.find_hash());
		if (it != stored.end()) return it->y;
	}
	int options = 0;
	pdd sum{ 0,0 };
	for (int i = 0; i < U; ++i) {
		if (s.B[i].y <= 0) break;
		state ss = s;
		ss.mv(i);
		pdd curans = find_ans(ss);
		sum.x += curans.x;
		sum.y += curans.y;
		++options;
	}
	return { sum.x / options, sum.y / options };
}

void solve_test() {
	int n, m;
	cin >> n >> m;
	state s;
	s.aA = 0;
	for (int i = 0; i < n; ++i) {
		cin >> s.A[i].x;
		s.A[i].y = s.A[i].x;
	}
	for (int i = n; i < U; ++i)
		s.A[i].y = s.A[i].x = 0;
	s.aB = 0;
	for (int i = 0; i < m; ++i) {
		cin >> s.B[i].x;
		s.B[i].y = s.B[i].x;
	}
	for (int i = m; i < U; ++i)
		s.B[i].y = s.B[i].x = 0;
	s.f = true;
	state ss = s;
	swap(ss.A, ss.B);
	ss.f = false;
	pdd ans;
	if (n > m)
		ans = find_ans(s);
	else if (n < m)
		ans = find_ans(ss);
	else {
		pdd ans1 = find_ans(s);
		pdd ans2 = find_ans(ss);
		ans = { (ans1.x + ans2.x) / 2, (ans1.y + ans2.y) / 2 };
	}
	cout << ans.x << '\n' << ans.y << '\n' << 1 - ans.x - ans.y << '\n';
}

int main()
{
#ifdef ONPC
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout << setprecision(22) << fixed;
	solve_test();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3644kb

input:

2 3
2 5
3 4 1

output:

0.1250000000000000000000
0.7500000000000000000000
0.1250000000000000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

6 6
1 1 4 5 1 4
1 1 4 5 1 4

output:

0.2418672839506172839592
0.2418672839506172839592
0.5162654320987654320545

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

7 7
1 1 1 1 1 1 1
1 1 1 1 1 1 1

output:

0.0000000000000000000000
0.0000000000000000000000
1.0000000000000000000000

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

1 7
7
1 1 1 1 1 1 1

output:

0.0000000000000000000000
0.0000000000000000000000
1.0000000000000000000000

result:

ok 3 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

2 3
736618938 652769331
328875880 97571721 44608905

output:

1.0000000000000000000000
0.0000000000000000000000
0.0000000000000000000000

result:

ok 3 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

5 4
53585130 731696211 668322278 611205195 158818781
569587984 776042583 745745433 330119007

output:

0.0668402777777777777808
0.6643518518518518518358
0.2688078703703703704105

result:

ok 3 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

7 2
578505806 551611151 92903265 403642038 542119417 57334031 307573613
897644535 168524310

output:

1.0000000000000000000000
0.0000000000000000000000
0.0000000000000000000000

result:

ok 3 numbers

Test #8:

score: -100
Wrong Answer
time: 2ms
memory: 3744kb

input:

5 6
113196606 64768263 772808463 787707989 500151952
481840741 676847825 4641268 431386165 847736311 169677832

output:

0.1365546553497942386792
0.5224712577160493827801
0.3409740869341563785679

result:

wrong answer 1st numbers differ - expected: '0.1363232', found: '0.1365547', error = '0.0002315'