QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30524#2455. Retribution!sinbad#AC ✓225ms17336kbC++174.7kb2022-04-29 20:35:182023-09-17 13:39:26

Judging History

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

  • [2023-09-17 13:39:26]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:225ms
  • 内存:17336kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 20:35:20]
  • 评测
  • 测评结果:100
  • 用时:287ms
  • 内存:17312kb
  • [2022-04-29 20:35:18]
  • 提交

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'