QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#691657 | #9412. Stop the Castle | 0x3fffffff | AC ✓ | 1ms | 3856kb | C++20 | 3.8kb | 2024-10-31 12:29:36 | 2024-10-31 12:29:38 |
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 + m;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) / 2,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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
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: 0ms
memory: 3856kb
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 5 1 7 1 26 33 28 44 45 42 44 0 5 29 33 27 41 44 21 9 1 26 15 1 32 10 0 0 0 0 6 23 10 23 44 12 25 29 27 35 34 29 46 0 3 20 30 43 28 32 17 0 -1 3 25 9 16 36 24 39 6 8 11 7 5 6 5 5 5 6 10 6 9
result:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3832kb
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 453 313 440 185 393 307 390 337 352 61 261 480 132 160 277 230 277 356 274 89 94 35 91 61 35 292 224 147 224 412 126 67 126 275 52 139 306 374 199 432 154 138 154 496 185 153 187 442 187 467 349 112 260 258 270 305 311 367 311 468 334 186 398 385 274 186 139 429 56 436 67 499 68 139 38 4 417 305 ...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
20 13 89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 8 128947560 120560639 264980960 4742...
output:
8 773363571 522193283 543529670 185921547 263974835 479445416 142917372 590766976 89287395 516114029 395304517 598813561 710278350 598813561 187924111 582720391 7 808969359 574744809 808969359 818037531 808969359 904126917 131614064 871951216 138082116 358274214 639043654 762966373 839408368 3547113...
result:
ok ok 20 cases (20 test cases)
Test #5:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
2 184 35763790 435860426 152681166 443483111 261932524 745277126 261932524 787982418 314305867 342102981 314305867 522593781 314305867 747023891 314305867 811404535 314305867 816914009 314305867 857896659 319901983 797458033 321347896 342102981 332550928 902179526 343207116 914408792 350635050 15515...
output:
160 995720397 582409334 883626548 787982418 846647902 909907721 814024114 419122314 814024114 445490406 814024114 461457354 814024114 499893628 814024114 645139797 814024114 802057256 814024114 857896659 814024114 908294159 813653133 815487777 812959730 433695683 812959730 526518374 812959730 773080...
result:
ok ok 2 cases (2 test cases)
Test #6:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
2 193 78368109 329329995 87932514 657474465 87932514 903492853 94608574 845872655 103602204 88649154 124431127 405860533 145262472 108198774 145262472 907127202 154400439 136367504 165270984 773451933 184157521 409828915 197728547 291882089 197728547 609623645 211750768 843867422 246178069 108396139...
output:
145 944222501 657489855 843018587 650775261 791054788 679561062 758554680 935856129 988331241 625394973 798222630 480642952 619662996 933251402 385064292 502303728 382558552 845363118 368273297 580019317 721810229 872055230 459002742 726497712 291242118 564718673 87932514 780483659 946078033 7894672...
result:
ok ok 2 cases (2 test cases)
Test #7:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
2 192 1075648 579875717 1075648 937648715 1393060 191616432 3957616 541362608 3957616 971879257 5415801 541362608 5887448 541362608 5887448 624842533 25767120 610618164 26193206 214214028 26193206 231445627 26727662 374314271 29550509 755417826 29550509 917592925 30033126 610618164 31134588 58188305...
output:
131 995510167 616550509 959874149 755417826 954450160 231445627 867509363 282047650 867509363 341084057 867509363 374314271 867509363 541362608 867509363 839148357 861709091 541362608 996654171 386404117 757703054 231445627 757703054 541362608 757703054 755417826 757703054 847220749 754755039 581883...
result:
ok ok 2 cases (2 test cases)
Test #8:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
20 14 378192988 147499872 378192988 837331700 449924898 147499872 449924898 837331700 592684636 147499872 592684636 837331700 783332532 147499872 783332532 837331700 378192988 197547597 783332532 197547597 378192988 343857831 783332532 343857831 378192988 576579017 783332532 576579017 2 449924898 19...
output:
15 783332532 172523734 783332532 270702714 783332532 460218424 783332532 706955358 378192988 172523734 378192988 270702714 378192988 460218424 378192988 706955358 580762760 576579017 414058943 837331700 521304767 837331700 688008584 837331700 414058943 147499872 521304767 147499872 688008584 1474998...
result:
ok ok 20 cases (20 test cases)
Test #9:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
2 200 8623893 3649468 8623893 989134714 24820918 3649468 24820918 989134714 43705451 3649468 43705451 989134714 45500146 3649468 45500146 989134714 58265855 3649468 58265855 989134714 112263159 3649468 112263159 989134714 126496650 3649468 126496650 989134714 137574156 3649468 137574156 989134714 14...
output:
249 956639323 4952387 956639323 8933110 956639323 17488709 956639323 26152612 956639323 30426606 956639323 33971968 956639323 51128190 956639323 75189901 956639323 108431886 956639323 140896961 956639323 161694450 956639323 177359477 956639323 187746597 956639323 213426472 956639323 233218080 956639...
result:
ok ok 2 cases (2 test cases)
Test #10:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
2 200 2691939 27674656 2691939 984614319 30225807 27674656 30225807 984614319 39388076 27674656 39388076 984614319 55883389 27674656 55883389 984614319 77258752 27674656 77258752 984614319 106874917 27674656 106874917 984614319 144383292 27674656 144383292 984614319 145360776 27674656 145360776 9846...
output:
216 643299496 441004197 631858791 257900116 630132600 206375958 562810007 376231503 347252805 540189713 754008138 390555088 446662965 383623456 538628510 293316179 496057717 490065400 523731402 243902652 2691939 48352248 2691939 114609279 2691939 168226626 2691939 182816064 2691939 197871776 2691939...
result:
ok ok 2 cases (2 test cases)
Test #11:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
2 200 1005937 7 3412691 7 5764908 7 7897785 7 8061992 7 12801501 7 18529696 7 22574605 7 25203351 7 34574958 7 34998216 7 40928451 7 49792193 7 55962320 7 59632864 7 62353373 7 62611196 7 65346591 7 71459320 7 71550121 7 72215989 7 82584263 7 86119549 7 96204862 7 96940713 7 97693112 7 102067050 7 1...
output:
199 2209314 7 4588799 7 6831346 7 7979888 7 10431746 7 15665598 7 20552150 7 23888978 7 29889154 7 34786587 7 37963333 7 45360322 7 52877256 7 57797592 7 60993118 7 62482284 7 63978893 7 68402955 7 71504720 7 71883055 7 77400126 7 84351906 7 91162205 7 96572787 7 97316912 7 99880081 7 103760846 7 10...
result:
ok ok 2 cases (2 test cases)
Extra Test:
score: 0
Extra Test Passed