QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771378#5444. Tavern Chessucup-team3702#RE 22ms11112kbC++142.6kb2024-11-22 12:19:362024-11-22 12:19:37

Judging History

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

  • [2024-11-22 12:19:37]
  • 评测
  • 测评结果:RE
  • 用时:22ms
  • 内存:11112kb
  • [2024-11-22 12:19:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, d, u) for(int i = d; i <= u; ++i)
const int _maxn = 7, _zinf = 1000000001;
int n, m, a[_maxn], b[_maxn];
struct node {
	int le[_maxn], ri[_maxn];
	long long lt[_maxn], rt[_maxn];
	node atak(int la, int ra, bool st) {
		if(st) {
			rt[ra] += a[la];
		} else {
			lt[la] += b[ra];
		}
		node re = *this;
		if((re . le[la] -= b[ra]) < 0) {
			re . le[la] = 0;
		}
		if((re . ri[ra] -= a[la]) < 0) {
			re . ri[ra] = 0;
		}
		return re;
	}
	int chek() {
		int la = 0, ra = 0;
		rep(i, 0, n - 1) {
			if(le[i]) {
				la = 1;
				break;
			}
		}
		rep(i, 0, m - 1) {
			if(ri[i]) {
				ra = 1;
				break;
			}
		}
		return la << 1 | ra;
	}
} orig;
bool operator<(node le, node ri) {
	rep(i, 0, n - 1) {
		if(le . le[i] != ri . le[i]) {
			return le . le[i] < ri . le[i];
		}
	}
	rep(i, 0, m - 1) {
		if(le . ri[i] != ri . ri[i]) {
			return le . ri[i] < ri . ri[i];
		}
	}
	rep(i, 0, n - 1) {
		if(le . lt[i] != ri . lt[i]) {
			return le . lt[i] < ri . lt[i];
		}
	}
	rep(i, 0, m - 1) {
		if(le . rt[i] != ri . rt[i]) {
			return le . rt[i] < ri . rt[i];
		}
	}
	return 0;
}
struct dats {
	double le, ri, bl;
	dats() {}
	dats(double fi, double se, double th) : le(fi), ri(se), bl(th) {}
};
dats operator+(dats le, dats ri) {
	return dats(le . le + ri . le, le . ri + ri . ri, le . bl + ri . bl);
}
dats operator/(dats le, int ri) {
	return dats(le . le / ri, le . ri / ri, le . bl / ri);
}
map<node, dats> maps[2];
dats dfs1(bool at, node st) {
	switch(st . chek()) {
		case 0 : return dats(0, 0, 1);
		case 1 : return dats(0, 1, 0);
		case 2 : return dats(1, 0, 0);
	}
	if(maps[at] . count(st)) {
		return maps[at][st];
	}
	int mi = _zinf, po, cn = 0;
	dats re(0, 0, 0);
	if(at) {
		rep(i, 0, m - 1) {
			if(st . ri[i] && mi > st . rt[i]) {
				mi = st . rt[i], po = i;
			}
		}
		rep(i, 0, n - 1) {
			if(st . le[i]) {
				re = re + dfs1(0, st . atak(i, po, at)), ++cn;
			}
		}
	} else {
		rep(i, 0, n - 1) {
			if(st . le[i] && mi > st . lt[i]) {
				mi = st . lt[i], po = i;
			}
		}
		rep(i, 0, m - 1) {
			if(st . ri[i]) {
				re = re + dfs1(1, st . atak(po, i, at)), ++cn;
			}
		}
	}
	return maps[at][st] = re / cn;
}
int main() {
	cin >> n >> m;
	rep(i, 0, n - 1) {
		cin >> a[i], orig . le[i] = a[i];
	}
	rep(i, 0, m - 1) {
		cin >> b[i], orig . ri[i] = b[i];
	}
	dats rans;
	if(n > m) {
		rans = dfs1(0, orig);
	} else if(n < m) {
		rans = dfs1(1, orig);
	} else {
		rans = (dfs1(0, orig) + dfs1(1, orig)) / 2;
	}
	printf("%.15lf\n%.15lf\n%.15lf\n", rans . le, rans . ri, rans . bl);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3
2 5
3 4 1

output:

0.125000000000000
0.750000000000000
0.125000000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 22ms
memory: 11112kb

input:

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

output:

0.241867283950617
0.241867283950617
0.516265432098766

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 9ms
memory: 7896kb

input:

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

output:

0.000000000000000
0.000000000000000
1.000000000000000

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

1 7
7
1 1 1 1 1 1 1

output:

0.000000000000000
0.000000000000000
1.000000000000000

result:

ok 3 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

2 3
736618938 652769331
328875880 97571721 44608905

output:

1.000000000000000
0.000000000000000
0.000000000000000

result:

ok 3 numbers

Test #6:

score: -100
Runtime Error

input:

5 4
53585130 731696211 668322278 611205195 158818781
569587984 776042583 745745433 330119007

output:


result: