QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#30524 | #2455. Retribution! | sinbad# | AC ✓ | 225ms | 17336kb | C++17 | 4.7kb | 2022-04-29 20:35:18 | 2023-09-17 13:39:26 |
Judging History
answer
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
// mt19937 mrand(random_device{}());
// int rnd(int x) { return mrand() % x; }
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
int lg2(int64 x) { return sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
};
} fast_ios_;
int sqr(int x) {
return x * x;
}
int main() {
int n, m, p;
cin >> n >> m >> p;
vector<array<int, 2>> a(n), b(m), c(p);
for (int i = 0; i < n; ++i) cin >> a[i][0] >> a[i][1];
for (int i = 0; i < m; ++i) cin >> b[i][0] >> b[i][1];
for (int i = 0; i < p; ++i) cin >> c[i][0] >> c[i][1];
vector<array<int, 3>> e;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
e.push_back({sqr(a[i][0] - b[j][0]) + sqr(a[i][1] - b[j][1]), i, j});
}
}
sort(e.begin(), e.end());
vector<bool> A(n), B(m), C(p);
double ret = 0;
for (auto& [d, i, j] : e) {
if (A[i] || B[j]) continue;
ret += sqrt(1.0 * d);
A[i] = B[j] = 1;
}
e.clear();
fill(A.begin(), A.end(), 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < p; ++j) {
e.push_back({sqr(a[i][0] - c[j][0]) + sqr(a[i][1] - c[j][1]), i, j});
}
}
sort(e.begin(), e.end());
for (auto& [d, i, j] : e) {
if (A[i] || C[j]) continue;
ret += sqrt(1.0 * d);
A[i] = C[j] = 1;
}
cout << ret << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
input:
2 2 2 1 0 2 0 0 0 3 0 1 1 2 1
output:
4.0000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1 1 1 5875 3435 -743 8951 2325 7352
output:
13901.6854602582
result:
ok found '13901.6854603', expected '13901.6854603', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 2 2 0 0 10 0 6 0 20 0 6 0 20 0
output:
48.0000000000
result:
ok found '48.0000000', expected '48.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
4 4 4 0 0 10 0 15 -15 1 40 5 0 0 -5 -5 0 0 5 5 0 0 -5 0 5 -5 0
output:
157.8224594073
result:
ok found '157.8224594', expected '157.8224594', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
4 4 4 0 0 10 0 15 -15 1 40 5 0 -5 0 0 -5 0 5 5 0 -5 0 0 5 0 -5
output:
150.8502157847
result:
ok found '150.8502158', expected '150.8502158', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
4 4 4 0 0 10 0 15 -15 1 40 5 0 0 5 0 -5 -5 0 5 0 0 5 -5 0 0 -5
output:
149.3111861943
result:
ok found '149.3111862', expected '149.3111862', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
4 4 4 0 0 10 0 15 -15 1 40 0 -5 5 0 -5 0 0 5 0 -5 5 0 0 5 -5 0
output:
145.4617796323
result:
ok found '145.4617796', expected '145.4617796', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
4 4 4 0 0 10 0 15 -15 1 40 0 -5 -5 0 5 0 0 5 0 -5 -5 0 0 5 5 0
output:
140.0285656000
result:
ok found '140.0285656', expected '140.0285656', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
4 4 4 0 0 10 0 15 -15 1 40 0 -5 0 5 5 0 -5 0 0 -5 0 5 -5 0 5 0
output:
150.8949936646
result:
ok found '150.8949937', expected '150.8949937', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 4 4 0 0 10 0 15 -15 1 40 -5 0 5 0 0 -5 0 5 -5 0 5 0 0 5 0 -5
output:
126.0840783547
result:
ok found '126.0840784', expected '126.0840784', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
4 4 4 0 0 10 0 15 -15 1 40 -5 0 0 -5 5 0 0 5 -5 0 0 -5 0 5 5 0
output:
126.0840783547
result:
ok found '126.0840784', expected '126.0840784', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 4 4 0 0 10 0 15 -15 1 40 -5 0 0 5 5 0 0 -5 -5 0 0 5 0 -5 5 0
output:
126.0840783547
result:
ok found '126.0840784', expected '126.0840784', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
4 4 4 0 0 10 0 15 -15 1 40 0 5 5 0 0 -5 -5 0 0 5 5 0 -5 0 0 -5
output:
136.9505064193
result:
ok found '136.9505064', expected '136.9505064', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
4 4 4 0 0 10 0 15 -15 1 40 0 5 0 -5 5 0 -5 0 0 5 0 -5 -5 0 5 0
output:
136.9505064193
result:
ok found '136.9505064', expected '136.9505064', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
4 4 4 0 0 10 0 15 -15 1 40 0 5 -5 0 5 0 0 -5 0 5 -5 0 0 -5 5 0
output:
136.9505064193
result:
ok found '136.9505064', expected '136.9505064', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3888kb
input:
5 5 5 0 0 10 10 20 20 30 30 40 40 10 0 20 10 30 20 40 30 50 40 0 10 10 20 20 30 30 40 40 50
output:
100.0000000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #17:
score: 0
Accepted
time: 20ms
memory: 4876kb
input:
200 500 500 9317 9422 967 -1586 4914 -1686 298 -2757 5733 7839 2366 -1911 -6760 -7344 -5277 -8055 -6719 1100 6048 9021 -2631 -1185 -9021 -2756 -871 -8829 5937 630 -4120 501 -2119 -4639 -3429 9773 -8790 -5080 -4588 -4404 -983 -4692 -2901 -7622 5147 1450 -6601 4971 5450 758 -4282 -8352 -3228 3634 -850...
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #18:
score: 0
Accepted
time: 10ms
memory: 4228kb
input:
100 300 500 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 1058 9474 105...
output:
1320642.6357890905
result:
ok found '1320642.6357891', expected '1320642.6357891', error '0.0000000'
Test #19:
score: 0
Accepted
time: 133ms
memory: 17152kb
input:
600 1000 1000 -5279 9183 -5142 2199 1159 8000 6190 3760 -2235 -3115 -3717 -4337 2385 -9717 1979 2349 -670 -4911 -5219 -3475 6690 852 4558 -2037 -3487 -9769 488 -2979 -3320 -615 -6510 -6853 3865 -4778 3686 -2060 -8277 9430 5648 7885 -967 -1666 -4585 9127 2337 -5555 -2880 -3590 3781 36 -9745 3021 6773...
output:
470049.3302835421
result:
ok found '470049.3302835', expected '470049.3302835', error '0.0000000'
Test #20:
score: 0
Accepted
time: 20ms
memory: 4808kb
input:
100 1000 1000 922 9101 3100 1580 1294 -7721 -6165 -8516 394 -2688 -4818 -639 -5290 -6133 -5489 -8166 -2548 -7234 -3512 -3708 -7119 -2390 -6967 3042 -5045 -1628 -5421 8596 -1425 -8296 9360 -3574 -3753 -5373 4029 673 -2627 -9196 9349 -8286 1699 6300 -844 -2833 7124 -5145 -7703 8708 -3414 -5303 1485 -6...
output:
69604.3478112928
result:
ok found '69604.3478113', expected '69604.3478113', error '0.0000000'
Test #21:
score: 0
Accepted
time: 35ms
memory: 6300kb
input:
200 1000 1000 -1619 9114 1049 7500 -3000 769 2127 3934 -4197 -2177 -4642 -1231 -4641 -3114 -1673 -4935 -7150 1734 -7717 -9152 9270 -9497 1090 -2435 -6345 -8752 -5055 -4473 -5422 -1092 -4397 -4337 819 -2418 -1269 6057 -671 -973 -7312 -9971 -8873 2983 -3826 9566 8980 -8070 -2999 425 1329 -8142 -5555 -...
output:
129789.1443608198
result:
ok found '129789.1443608', expected '129789.1443608', error '0.0000000'
Test #22:
score: 0
Accepted
time: 64ms
memory: 10108kb
input:
300 1000 1000 -646 9131 -9706 -1483 3867 6807 257 -504 -2170 -5156 -4422 -1970 -212 -3491 6715 -5045 -561 -8015 -8399 1 1138 2045 -9372 7103 -3820 -1273 -979 3765 -1801 3338 2983 -9333 -1657 1701 -7891 -3596 2199 9306 -7712 157 -9746 -1164 -7127 -7702 -5085 615 -8928 2306 3108 -3074 5646 -8760 -6340...
output:
209890.4458796818
result:
ok found '209890.4458797', expected '209890.4458797', error '0.0000000'
Test #23:
score: 0
Accepted
time: 88ms
memory: 11308kb
input:
400 1000 1000 -3710 9154 -5103 -7506 -1414 -6528 -233 8516 329 -646 -4113 -3006 -2693 408 -2990 -773 -2657 -4130 -7566 -7185 -1567 -3583 6962 -6098 -4712 2644 -3954 1852 -2944 7753 -133 -1094 1769 914 -4395 2209 -336 -9072 2708 -558 -2288 -6969 1698 -6005 -5455 1453 -8888 -9955 -2742 -2192 -6673 559...
output:
286710.9630597470
result:
ok found '286710.9630597', expected '286710.9630597', error '0.0000000'
Test #24:
score: 0
Accepted
time: 106ms
memory: 10188kb
input:
500 1000 1000 -2737 9170 -3092 -3722 -1781 -490 -2102 -8690 2357 -3625 -3893 -3745 1736 32 -1837 -883 -8835 -1112 -1014 1969 -9699 7959 9267 -9327 -2187 -2645 121 -2676 677 -7818 -5520 -6090 -707 -7734 8984 -7444 2534 1207 2308 2336 -3162 1651 -1604 -3273 481 -2629 -7583 4692 -8196 2876 -2706 -3116 ...
output:
395858.1495181319
result:
ok found '395858.1495181', expected '395858.1495181', error '0.0000000'
Test #25:
score: 0
Accepted
time: 152ms
memory: 17336kb
input:
700 1000 1000 4947 9196 -7193 -4647 -3136 -3511 -5519 -3791 5941 -2604 -3541 -4928 3034 -6698 -6971 -7187 -5272 4057 -9424 3848 3078 979 -152 -7513 7980 -4126 854 3952 -82 6589 -266 5151 8438 5411 -1611 -9443 912 -2348 8989 -6567 1228 -4983 -333 1525 4192 4287 1824 -4639 -4243 4431 3216 9158 -1758 -...
output:
637650.9744090202
result:
ok found '637650.9744090', expected '637650.9744090', error '0.0000000'
Test #26:
score: 0
Accepted
time: 177ms
memory: 16456kb
input:
800 1000 1000 -5351 9219 -2590 2097 -8416 -9612 6758 5229 -4327 1906 -3232 -5964 553 4435 -3910 4320 -7367 -4825 -8592 -3338 -6861 -4649 -3819 -714 -145 -209 -2121 2039 -8460 -8997 -3382 -6611 -8137 4624 1885 -3637 -1623 -725 6642 -7282 8685 9212 1259 -9544 -8945 5125 1864 -4133 2674 -1922 -9104 351...
output:
759351.8838631257
result:
ok found '759351.8838631', expected '759351.8838631', error '0.0000000'
Test #27:
score: 0
Accepted
time: 200ms
memory: 16524kb
input:
900 1000 1000 2856 9235 6656 -6886 -1550 9193 -7879 790 -2300 -1073 -3012 -6703 4982 -3176 4478 -3025 -778 -1807 -9273 -6952 -7759 6893 -1514 -3942 9614 -5497 1955 -2489 -4839 -4567 -8770 8394 2154 8743 -4737 6710 1247 9554 -992 -4388 -4955 5066 -2043 -6812 9759 1043 -4065 -2253 4453 -9621 -5136 -51...
output:
987999.2787579860
result:
ok found '987999.2787580', expected '987999.2787580', error '0.0000000'
Test #28:
score: 0
Accepted
time: 225ms
memory: 16076kb
input:
1000 1000 1000 1810 9255 -37 1995 2010 5545 7326 6698 -6420 -308 -2748 -7591 5956 -1415 -9799 -944 -1298 -4739 803 4033 -411 9850 -4961 609 -9571 -3416 2505 -5710 6401 2622 -254 -6368 -7371 -5975 7317 -5214 -2203 1887 7635 -9682 -1663 90 -5665 -8215 -7459 -4196 6608 -4677 8802 -3879 4305 4006 4323 -...
output:
1825100.3802688522
result:
ok found '1825100.3802689', expected '1825100.3802689', error '0.0000000'
Test #29:
score: 0
Accepted
time: 220ms
memory: 17112kb
input:
1000 1000 1000 -6902 -3387 2189 -4785 2673 -6027 8785 -9963 -626 -4522 1659 -2371 -7257 -6932 -9375 4135 9988 -2547 -5581 -4344 -555 4923 -4608 -4641 5912 -8176 6497 7117 -5931 -8260 -9677 -8546 -3542 -3892 -6043 -1941 9901 -1589 -9514 -8317 4047 3117 728 -6010 -6818 6729 -4233 -106 3918 4455 -6945 ...
output:
1671206.0961421935
result:
ok found '1671206.0961422', expected '1671206.0961422', error '0.0000000'