QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#74231#5433. Absolute DifferenceXKErrorWA 6ms4164kbC++142.8kb2023-01-31 10:17:372023-01-31 10:17:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-31 10:17:39]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:4164kb
  • [2023-01-31 10:17:37]
  • 提交

answer

#include <bits/stdc++.h>

#define maxn 200005
#define db double
#define int long long

using namespace std;

int n, m;

struct node{
	int l, r;
	db prb;
	node () {}
	node (int x, int y, db z = 0) {
		l = x, r = y, prb = z;
	}
	int len() {
		return r - l;
	}
	db mid() {
		return (l + r) / 2.0;
	}
	bool operator ==(const node x) {
		return l == x.l && r == x.r;
	}
};

db ans;

void solve(vector<node> &a, vector<node> &b, int l, int r) {
	if (a.empty() || b.empty()) return;
	if (a.size() == 1 && b.size() == 1) {
		if (a[0] == b[0]) {
			ans += a[0].len() * a[0].prb * b[0].prb / 3;
			return;
		}
		if (a[0].len() == 0 && b[0].len() == 0) {
			ans += abs(a[0].l - b[0].l) * a[0].prb * b[0].prb;
			return;
		}
		if (a[0].len() == 0) {
			ans += fabs(a[0].l - b[0].mid()) * a[0].prb * b[0].prb;
			return;
		}
		if (b[0].len() == 0) {
			ans += fabs(b[0].l - a[0].mid()) * a[0].prb * b[0].prb;
			return;
		}
	}
	int mid = (l + r) >> 1;
//	cout<<mid<<" "<<a[0].l<<" "<<a[0].r<<" "<<b[0].l<<" "<<b[0].r<<endl;
	vector<node> la, ra, lb, rb;
	for (auto x : a) {
		if (x.r <= mid) la.push_back(x);
		else if (x.l >= mid) ra.push_back(x);
		else {
			auto s = node(x.l, mid, x.prb * (mid - x.l) / (x.r - x.l));
			auto t = node(mid, x.r, x.prb * (x.r - mid) / (x.r - x.l));
			la.push_back(s);
			ra.push_back(t);
		}
	}
	for (auto x : b) {
		if (x.r <= mid) lb.push_back(x);
		else if (x.l >= mid) rb.push_back(x);
		else {
			auto s = node(x.l, mid, x.prb * (mid - x.l) / (x.r - x.l));
			auto t = node(mid, x.r, x.prb * (x.r - mid) / (x.r - x.l));
			lb.push_back(s);
			rb.push_back(t);
		}
	}
	db s = 0, t = 0;
	db sp = 0, tp = 0;
	if (la.size() && rb.size()) {
		for (auto x : la) s += x.mid() * x.prb, sp += x.prb; 
		for (auto x : rb) t += x.mid() * x.prb, tp += x.prb;
//		cout<<"ED:"<<s<<" "<<t<<endl;
		ans += t * sp - s * tp;
		s = t = 0;
	}
	if (lb.size() && ra.size()) {
		for (auto x : la) s += x.mid() * x.prb, sp += x.prb; 
		for (auto x : rb) t += x.mid() * x.prb, tp += x.prb;
//		cout<<"ED:"<<s<<" "<<t<<endl;
		ans += t * sp - s * tp;
//		ans += t - s;
	}
	solve(la, lb, l, mid);
	solve(ra, rb, mid, r);
}

vector<node> a, b;

signed main() {
	scanf("%lld%lld", &n, &m);
	int sa = 0, sb = 0;
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%lld%lld", &x, &y);
		a.push_back(node(x, y));
		sa += y - x;
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%lld%lld", &x, &y);
		b.push_back(node(x, y));
		sb += y - x;
	}
	if (sa == 0) for (auto &x : a) x.prb = 1.0 / n;
	else for (auto &x : a) x.prb = x.len() * 1.0 / sa;
	
	if (sb == 0) for (auto &x : b) x.prb = 1.0 / m;
	else for (auto &x : b) x.prb = x.len() * 1.0 / sb;
	
	solve(a, b, (int)-1e9, (int)1e9);
	
	printf("%.12lf\n", ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3708kb

input:

1 1
0 1
0 1

output:

0.333333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

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

input:

1 1
0 1
1 1

output:

0.500000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 4ms
memory: 3632kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666626930

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.499999880791

result:

ok found '1000000000.499999881', expected '1000000000.500000000', error '0.000000000'

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.000000000000

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 6ms
memory: 4164kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

10513.818751537108

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '10513.8187515', error = '0.5652278'