QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30523#2455. Retribution!sinbad#WA 29ms4976kbC++174.7kb2022-04-29 20:33:442022-04-29 20:33:45

Judging History

你现在查看的是测评时间为 2022-04-29 20:33:45 的历史记录

  • [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: 3ms
memory: 3760kb

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: 2ms
memory: 3768kb

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: 3ms
memory: 3704kb

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: 3ms
memory: 3856kb

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: 3ms
memory: 3720kb

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: 3ms
memory: 3848kb

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: 3ms
memory: 3776kb

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: 3ms
memory: 3712kb

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

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: 1ms
memory: 3808kb

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: 3ms
memory: 3852kb

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: 3ms
memory: 3908kb

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: 2ms
memory: 3764kb

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: 3ms
memory: 3700kb

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: 3ms
memory: 3756kb

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

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: 29ms
memory: 4976kb

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: 14ms
memory: 4296kb

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:

1343583.1444669096

result:

wrong answer 1st numbers differ - expected: '1320642.6357891', found: '1343583.1444669', error = '0.0173707'