QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#801067#7013. Rikka with AntsSGColinAC ✓8ms3916kbC++203.0kb2024-12-06 18:09:332024-12-06 18:09:34

Judging History

This is the latest submission verdict.

  • [2024-12-06 18:09:34]
  • Judged
  • Verdict: AC
  • Time: 8ms
  • Memory: 3916kb
  • [2024-12-06 18:09:33]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 57;

int dis[N];

inline void work() {
	int n = rd();
	rep(i, 1, n) dis[i] = rd();
	int s1 = rd(), t1 = rd(), s2 = rd(), t2 = rd();
	auto check = [&](int x, int s, int t) {
		if (s > t) return (x >= s || x < t);
		else return (x >= s && x < t);
	};
	auto calc = [&](int s, int t, int ss, int tt) {
		int ret = 0;
		while (s != t) {
			ret += dis[s];
			if (check(s, ss, tt)) ret += dis[s] * 2;
			s = (s == n ? 1 : s + 1);
		}
		return ret;
	};
	double a1 = calc(s1, t1, s2, t2);
	double a2 = calc(s1, t1, t2, s2);
	double a3 = calc(t1, s1, s2, t2);
	double a4 = calc(t1, s1, t2, s2);
	
	double b1 = calc(s2, t2, s1, t1);
	double b2 = calc(t2, s2, s1, t1);
	double b3 = calc(s2, t2, t1, s1);
	double b4 = calc(t2, s2, t1, s1);

	bool fl = true;

	double p1 = -1;
	double up = a4 - a2, dn = a1 - a2 - a3 + a4;
	if (dn == 0 || (up < 0) != (dn < 0) || abs(up) >= abs(dn)) fl = false;
	else p1 = 1.0 * up / dn;

	double p2 = -1;
	up = b4 - b3;
	dn = b1 - b2 - b3 + b4;
	if (dn == 0 || (up < 0) != (dn < 0) || abs(up) >= abs(dn)) fl = false;
	else p2 = 1.0 * up / dn;

	swap(p1, p2);


	if (!fl) {
		// p1 = 1
		if (b1 == b2) {
			if (a1 <= a3) {
				// -> p1 = 1, p2 = 1
				printf("%.12lf %.12lf\n", a1, b1);
				return;
			}
			if (a2 <= a4) {
				// -> p1 = 1, p2 = 0
				printf("%.12lf %.12lf\n", a2, b2);
				return;
			}
		} 
		else if (b1 < b2) { // p2 = 1
			if (a1 <= a3) {
				// -> p1 = 1, p2 = 1
				printf("%.12lf %.12lf\n", a1, b1);
				return;
			}
		} else {
			if (a2 <= a4) {
				// -> p1 = 1, p2 = 0
				printf("%.12lf %.12lf\n", a2, b2);
				return;
			}
		}

		//p1 = 0
		if (b3 == b4) {
			if (a3 <= a1) {
				// -> p1 = 0, p2 = 1
				printf("%.12lf %.12lf\n", a3, b3);
				return;
			}
			if (a4 <= a2) {
				// -> p1 = 0, p2 = 0
				printf("%.12lf %.12lf\n", a4, b4);
				return;
			}
		} 
		else if (b3 < b4) { // p2 = 1
			if (a3 <= a1) {
				// -> p1 = 0, p2 = 1
				printf("%.12lf %.12lf\n", a3, b3);
				return;
			}
		} else {
			if (a4 <= a2) {
				// -> p1 = 0, p2 = 0
				printf("%.12lf %.12lf\n", a4, b4);
				return;
			}
		}
		while (true) {++p1; if (p1 > p2) ++p2;}
	}

	double v1 = a1 * p1 * p2 + a2 * p1 * (1 - p2) + a3 * p2 * (1 - p1) + a4 * (1 - p1) * (1 - p2);
	double v2 = b1 * p1 * p2 + b2 * p1 * (1 - p2) + b3 * p2 * (1 - p1) + b4 * (1 - p1) * (1 - p2);

	printf("%.12lf %.12lf\n", v1, v2);
}

int main() {
	per(t, rd(), 1) work();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
5
1 5 2 4 3
1 2 3 4
5
1 5 2 4 3
1 3 2 4

output:

1.000000000000 2.000000000000
14.666666666667 14.666666666667

result:

ok 2 cases

Test #2:

score: 0
Accepted
time: 8ms
memory: 3864kb

input:

5000
5
8 22 47 25 13
3 5 3 1
20
9 24 41 8 23 31 48 15 46 5 17 36 29 40 36 43 34 33 29 26
16 4 15 5
3
8 22 33
1 2 2 3
26
18 44 37 21 44 44 5 15 43 44 44 37 19 10 22 14 41 37 42 18 14 34 3 17 30 42
13 2 13 15
26
31 31 41 11 35 49 13 29 33 11 27 6 16 25 47 40 2 33 27 35 35 29 48 35 5 7
17 3 13 3
26
30 ...

output:

72.000000000000 30.000000000000
571.628865979381 571.628865979381
8.000000000000 22.000000000000
378.000000000000 29.000000000000
728.898876404494 728.898876404494
356.000000000000 103.000000000000
509.916981132075 509.916981132075
87.000000000000 63.000000000000
80.000000000000 36.000000000000
157....

result:

ok 5000 cases