QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#691615 | #9412. Stop the Castle | 0x3fffffff | WA | 1ms | 3656kb | C++20 | 3.8kb | 2024-10-31 12:15:41 | 2024-10-31 12:15:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;cin >> n;
unordered_map<int, vector<array<int, 2>>>mpx, mpy;
for (int i = 1;i <= n;i++) {
int x, y;cin >> x >> y;
mpx[x].push_back({ y,1 });
mpy[y].push_back({ x,1 });
}
int m;cin >> m;
for (int i = 1;i <= m;i++) {
int x, y;cin >> x >> y;
mpx[x].push_back({ y,0 });
mpy[y].push_back({ x,0 });
}
vector<array<int, 3>>A, B;
for (auto& [x, vec] : mpx) {
sort(vec.begin(), vec.end());
for (int j = 1;j < vec.size();j++) {
auto [y1, op1] = vec[j - 1];
auto [y2, op2] = vec[j];
if (op1 and op2) {
if (y1 + 1 == y2) { cout << "-1\n";return; }
A.push_back({ x,y1,y2 });
}
}
}
for (auto& [y, vec] : mpy) {
sort(vec.begin(), vec.end());
for (int j = 1;j < vec.size();j++) {
auto [x1, op1] = vec[j - 1];
auto [x2, op2] = vec[j];
if (op1 and op2) {
if (x1 + 1 == x2) { cout << "-1\n";return; }
B.push_back({ y,x1,x2 });
}
}
}
n = A.size(), m = B.size();
vector<vector<int>>e(n + m + 3);
vector<int>match(n + m + 3);
// for (auto [x, y, z] : A) {
// cout << x << " " << y << " " << z << "\n";
// }
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
auto [x, y1, y2] = A[i - 1];
auto [y, x1, x2] = B[j - 1];
if (x >= x1 and x <= x2 and y >= y1 and y <= y2) {
// cout << x << " " << y1 << " " << y2 << "\n";
// cout << y << " " << x1 << " " << x2 << "\n";
e[i].push_back(j + n);
}
}
}
// cout << "\n";
vector<int>vis(n + m + 3);
auto dfs = [&](auto&& ff, int u)->bool {
for (int v : e[u]) {
if (!vis[v]) {
vis[v] = 1;
if (match[v] == 0 || ff(ff, match[v])) {
match[v] = u;
return 1;
}
}
}
return 0;
};
for (int i = 1;i <= n;i++) {
fill(vis.begin(), vis.end(), 0);
dfs(dfs, i);
}
for (int i = 1;i <= n;i++) {
auto [x, y1, y2] = A[i - 1];
// cout << x << " " << y1 << " " << y2 << "\n";
// cout << match[i] << "\n";
if (match[i]) {
match[match[i]] = i;
}
}
for (int i = 1;i <= m;i++) {
auto [y, x1, x2] = B[i - 1];
// cout << y << " " << x1 << " " << x2 << "\n";
// cout << match[i + n] << "\n";
if (match[i + n]) {
match[match[i + n]] = i + n;
}
}
vector<int>ok(n + m + 3);
vector<array<int, 2>>ans;
for (int i = 1;i <= n;i++) {
if (match[i]) {
auto [x, y1, y2] = A[i - 1];
auto [y, x1, x2] = B[match[i] - n - 1];
ans.push_back({ x,y });
ok[i] = ok[match[i]] = 1;
}
else {
auto [x, y1, y2] = A[i - 1];
ans.push_back({ x,(y1 + y2) / 2 });
}
}
for (int j = 1;j <= m;j++) {
if (!ok[j + n]) {
auto [y, x1, x2] = B[j - 1];
ans.push_back({ x1 + x2 >> 1,y });
}
}
cout << ans.size() << "\n";
for (auto [x, y] : ans) {
cout << x << " " << y << "\n";
}
// cout << "\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin >> tt;
while (tt--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
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: -100
Wrong Answer
time: 1ms
memory: 3564kb
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 35 38 24 12 37 18 5 16 11 16 31 21 6 23 26 35 50 0 1 29 10 0 1 43 28 4 1 7 1 26 33 28 44 44 0 5 29 33 27 41 44 21 9 1 26 15 1 32 10 0 0 0 0 5 23 10 23 46 12 25 29 34 35 25 0 3 20 30 43 28 32 17 0 -1 3 25 9 16 39 12 36 6 8 11 7 5 6 5 5 5 6 10 6 9
result:
wrong answer Duplicated position (44, 44) (test case 7)