QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#607938#5433. Absolute DifferenceLuuuWA 2ms4268kbC++205.7kb2024-10-03 17:11:202024-10-03 17:11:20

Judging History

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

  • [2024-10-03 17:11:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4268kb
  • [2024-10-03 17:11:20]
  • 提交

answer

#include <bits/stdc++.h>  
using namespace std;  

#define int long long  

using db = long double;

#define fi first
#define se second

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

    cout << fixed << setprecision(20);

	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> a(n), b(m);
	for (auto &[l, r] : a) {
		cin >> l >> r;
	}
	for (auto &[l, r] : b) {
		cin >> l >> r;
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	auto check = [&](const vector<pair<int, int>> &t) {
		for (auto [x, y] : t) {
			if (x != y) {
				return true;
			}
		}
		return false;
 	};

 	auto work = [&](const vector<pair<int, int>> &t) {
 		vector<pair<int, int>> ret;
 		for (auto [x, y] : t) {
 			if (x != y) {
 				ret.push_back({x, y});
 			}
 		}
 		return ret;
 	};

 	bool oka = check(a), okb = check(b);
 	if (oka) {
 		a = work(a);
 		n = a.size(); 
 	} 
 	if (okb) {
 		b = work(b);
 		m = b.size();
 	}

 	if (!oka && !okb) {
 		vector<int> s(m + 1);
 		for (int i = 1; i <= m; i++) {
 			s[i] = s[i - 1] + b[i - 1].fi;
 		}
 		auto query = [&](int ql, int qr) {
 			return s[qr] - s[ql - 1];
 		};
 		db ans = 0;
 		for (auto [x, y] : a) {
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].fi <= x) {
 					l = mid;
 				} else {
 					r = mid;
 				}
 			} 
 			if (l == -1) {
 				continue;
 			}
 			ans += (l + 1) * x - query(1, l + 1);
 		}

		for (auto [x, y] : a) {
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].fi >= x) {
 					r = mid;
 				} else {
 					l = mid;
 				}
 			} 
 			if (r == m) {
 				continue;
 			}
 			ans += query(r + 1, m) - (m - r) * x;
 		}
 		
 		ans /= n, ans /= m;

 		cout << ans << "\n";

 		return 0;
 	}

 	if (oka && !okb) {
 		swap(oka, okb);
 		swap(a, b);
 	}

 	if (!oka && okb) {
 		set<int> s;
 		for (auto [x, y] : a) {
 			s.insert(x);
 		}
 		for (auto [x, y] : b) {
 			s.insert(x);
 			s.insert(y);
 		}
 		vector<int> p(s.begin(), s.end());

 		vector<pair<int, int>> nb;
 		db L = 0;
 		for (int i = 1; i < p.size(); i++) {
 			int x = p[i - 1], y = p[i];
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].fi <= x) {
 					l = mid;
 				} else {
 					r = mid;
 				}
 			}
 			if (l == -1 || b[l].se < y) {
 				continue;
 			}
 			nb.push_back({x, y});
 			L += (y - x);
 		}
 		b = nb;
 		m = b.size();
 		vector<db> s1(m + 1), s2(m + 1);
 		for (int i = 1; i <= m; i++) {
 			s1[i] = s1[i - 1] + (b[i - 1].se - b[i - 1].fi);
 			s2[i] = s2[i - 1] + 1.0 * (b[i - 1].se - b[i - 1].fi) * (b[i - 1].fi + b[i - 1].se) / 2;
 		}
 		auto qry1 = [&](int ql, int qr) {
 			return s1[qr] - s1[ql - 1];
 		};
 		auto qry2 = [&](int ql, int qr) {
 			return s2[qr] - s2[ql - 1];
 		};
 		db ans = 0;
 		for (auto [x, y] : a) {
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].se <= x) {
 					l = mid;
 				} else {
 					r = mid;
 				}
 			}
 			if (l == -1) {
 				continue;
 			}
 			ans += x * qry1(1, l + 1) - qry2(1, l + 1);	
 		}
 		for (auto [x, y] : a) {
 			int l = -1, r = m;
 			while (l + 1 != r) {
 				int mid = (l + r) / 2;
 				if (b[mid].fi >= x) {
 					r = mid;
 				} else {
 					l = mid;
 				}
 			}
 			if (r == m) {
 				continue;
 			}
 			ans += qry2(r + 1, m) - x * qry1(r + 1, m);	
 		}

 		ans /= n;
 		ans /= L;
 	
 		cout << ans << "\n";
 		return 0;
 	}

 	set<int> s;
	for (auto [x, y] : a) {
		s.insert(x);
		s.insert(y);
	}
	for (auto [x, y] : b) {
		s.insert(x);
		s.insert(y);
	}

	vector<int> p(s.begin(), s.end());

	vector<pair<int, int>> na;
	vector<pair<int, int>> nb;
	
	db La = 0, Lb = 0;
	for (int i = 1; i < p.size(); i++) {
		int x = p[i - 1], y = p[i];
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (a[mid].fi <= x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		if (l == -1 || a[l].se < y) {
			continue;
		}
		na.push_back({x, y});
		La += (y - x);
	}
	for (int i = 1; i < p.size(); i++) {
		int x = p[i - 1], y = p[i];
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (b[mid].fi <= x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		if (l == -1 || b[l].se < y) {
			continue;
		}
		nb.push_back({x, y});
		Lb += (y - x);
	}

	a = na;
	n = a.size();
	b = nb;
	m = b.size();

	set<pair<int, int>> sb;
	for (auto [x, y] : b) {
		sb.insert({x, y});
	}

	vector<db> s1(m + 1), s2(m + 1);
	for (int i = 1; i <= m; i++) {
		s1[i] = s1[i - 1] + (b[i - 1].se - b[i - 1].fi);
		s2[i] = s2[i - 1] + 1.0 * (b[i - 1].se - b[i - 1].fi) * (b[i - 1].fi + b[i - 1].se) / 2;
	}

	auto qry1 = [&](int ql, int qr) {
		return s1[qr] - s1[ql - 1];
	};
	auto qry2 = [&](int ql, int qr) {
		return s2[qr] - s2[ql - 1];
	};
	
	db ans = 0;
	for (auto [x, y] : a) {
		if (sb.count({x, y})) {
			ans += 1.0 * (y - x) * (y - x) * (y - x) / 3 / La / Lb;
		}
	}

	for (auto [x, y] : a) {
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (b[mid].se <= x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		// if (l == -1) {
		// 	continue;
		// }
		ans += (y - x) * (0.5 * (x + y) * qry1(1, l + 1) - qry2(1, l + 1)) / La / Lb;	
	}
	for (auto [x, y] : a) {
		int l = -1, r = m;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (b[mid].fi >= y) {
				r = mid;
			} else {
				l = mid;
			}
		}
		// if (r == m) {
		// 	continue;
		// }
		
		ans += (y - x) * (qry2(r + 1, m) - 0.5 * (x + y) * qry1(r + 1, m)) / La / Lb;
	}

	cout << ans << "\n";

    return 0;
}  
  

詳細信息

Test #1:

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

input:

1 1
0 1
0 1

output:

0.33333333333333331483

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.50000000000000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666662966599687934

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.00000000000000000000

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.00000000000000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.50000000000000000000

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.00000000052386894822

result:

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

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.00000000000000000000

result:

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

Test #9:

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

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:

6708.10713162254419872355

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '6708.1071316', error = '0.0013414'