QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617313 | #9412. Stop the Castle | lonelywolf | WA | 1ms | 3688kb | C++20 | 2.8kb | 2024-10-06 14:52:39 | 2024-10-06 14:52:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
map<int, vector<pair<int, int>>> xr, yr;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
xr[x].push_back({y, 0});
yr[y].push_back({x, 0});
}
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
xr[x].push_back({y, 1});
yr[y].push_back({x, 1});
}
using Point = pair<int, int>;
vector<pair<Point, Point>> ls;
for (auto &[x, v] : xr) {
sort(v.begin(), v.end());
for (int i = 1; i < v.size(); i++) {
if (v[i].second == 0 && v[i - 1].second == 0) {
int l = v[i - 1].first + 1, r = v[i].first - 1;
if (l > r) {
cout << -1 << "\n";
return;
}
ls.push_back({{x, l}, {x, r}});
}
}
}
for (auto &[y, v] : yr) {
sort(v.begin(), v.end());
for (int i = 1; i < v.size(); i++) {
if (v[i].second == 0 && v[i - 1].second == 0) {
int l = v[i - 1].first + 1, r = v[i].first - 1;
if (l > r) {
cout << -1 << "\n";
return;
}
ls.push_back({{l, y}, {r, y}});
}
}
}
// for (auto [a, b] : ls) {
// cout << "(" << a.first << ", " << a.second << ") " << "(" << b.first << ", " << b.second << ") \n";
// }
auto ins = [&](pair<Point, Point> a, pair<Point, Point> b) {
int x = a.first.first, y1 = a.first.second, y2 = a.second.second;
int y = b.first.second, x1 = b.first.first, x2 = b.second.first;
if (x == a.second.first && y != b.second.second) {
return false;
}
if (y < y1 || y > y2) {
return false;
}
if (x < x1 || x > x2) {
return false;
}
return true;
};
vector<vector<int>> g(ls.size(), vector<int>(ls.size()));
vector<int> f(ls.size());
int ans = 0;
for (int i = 0; i < ls.size(); i++) {
for (int j = i + 1; j < ls.size(); j++) {
if (ins(ls[i], ls[j])) {
g[i][j] = g[j][i] = 1;
ans++;
f[i]++, f[j]++;
}
}
}
vector<Point> a;
for (int i = 0; i < ls.size(); i++) {
if (f[i] == 0) {
ans++;
a.push_back(ls[i].first);
}
if (f[i] == 1) {
for (int j = i + 1; j < ls.size(); j++) {
if (g[i][j]) {
a.push_back({ls[i].first.first, ls[j].first.second});
}
}
continue;
}
for (int j = i + 1; j < ls.size(); j++) {
if (!g[i][j]) {
continue;
}
if (f[j] >= 2) {
g[i][j] = g[j][i] = 0;
f[i]--, f[j]--;
ans--;
}
if (f[i] < 2) {
continue;
}
}
for (int j = i + 1; j < ls.size(); j++) {
if (g[i][j]) {
a.push_back({ls[i].first.first, ls[j].first.second});
}
}
}
cout << ans << "\n";
for (auto [x, y] : a) {
cout << x << " " << y << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
4 7 1 3 6 6 4 7 2 1 6 3 4 1 2 6 3 3 4 6 4 3 1 2 1 1 2 2 0 3 1 1 1 3 3 3 1 1 2 3 1 1 1 3 2 3 0
output:
2 2 3 4 6 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
21 11 3 5 18 6 19 12 27 48 28 38 30 12 33 18 42 18 43 38 45 46 48 34 3 2 6 24 4 41 45 15 11 6 15 27 16 9 16 14 16 48 19 26 25 12 27 26 28 4 31 40 32 6 33 50 37 50 46 11 50 29 17 1 49 4 9 9 15 9 22 11 31 11 46 14 28 17 5 17 49 18 43 20 31 30 46 33 11 33 33 34 15 36 6 47 10 2 16 46 36 30 11 7 34 7 41 ...
output:
3 20 12 34 18 29 38 5 16 10 16 15 12 6 20 26 34 50 0 1 16 10 0 1 43 22 5 1 3 1 13 33 10 44 45 42 44 0 5 27 41 29 26 44 4 8 1 21 15 1 32 9 0 0 0 0 6 12 11 23 10 23 44 29 21 35 34 24 46 0 3 20 30 43 25 31 17 0 -1 3 16 36 25 7 17 39 6 5 5 6 5 7 5 8 9 8 10 8 11
result:
ok ok 21 cases (21 test cases)
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3688kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
46 35 276 52 139 126 275 154 496 185 67 187 433 187 467 199 160 199 432 224 35 224 61 224 393 260 275 261 468 274 67 277 189 306 374 311 147 311 177 311 356 311 455 334 367 352 61 352 138 390 308 393 112 393 153 393 186 393 305 393 307 440 179 453 251 11 4 38 25 240 35 52 67 57 139 271 186 278 272 4...
result:
wrong answer There are still 8 pairs of castles which can attack each other (test case 1)