QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#30523 | #2455. Retribution! | sinbad# | WA | 29ms | 4976kb | C++17 | 4.7kb | 2022-04-29 20:33:44 | 2022-04-29 20:33:45 |
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(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'