QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30523#2455. Retribution!sinbad#WA 20ms4960kbC++174.7kb2022-04-29 20:33:442023-09-17 13:39:26

Judging History

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

  • [2023-09-17 13:39:26]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:20ms
  • 内存:4960kb
  • [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:33:45]
  • 评测
  • 测评结果:0
  • 用时:29ms
  • 内存:4976kb
  • [2022-04-29 20:33:44]
  • 提交

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(m);
  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: 3824kb

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: 3820kb

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: 4064kb

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: 3988kb

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: 3888kb

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: 3836kb

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: 4052kb

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: 4060kb

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: 3884kb

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: 3824kb

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: 3832kb

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: 3768kb

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: 3884kb

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: 3864kb

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: 3828kb

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: 0ms
memory: 3820kb

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: 4960kb

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: -100
Wrong Answer
time: 9ms
memory: 4256kb

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:

1354253.6983182053

result:

wrong answer 1st numbers differ - expected: '1320642.6357891', found: '1354253.6983182', error = '0.0254505'