QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665342 | #9412. Stop the Castle | RUOHUI | AC ✓ | 1ms | 3880kb | C++20 | 3.9kb | 2024-10-22 11:33:55 | 2024-10-22 11:33:56 |
Judging History
answer
#include "bits/stdc++.h"
#define int long long
#define ull unsigned long long
#define double long double
#define PII pair<int,int>
#define TIII tuple<int,int,int>
#define LL __int128
#define eps 1e-6
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 2e5 + 10, M = 2e6 + 10, mod = 1e9 + 7, inf = 1e18;
int n, m;
void solve()
{
//记录每行每列有哪些城堡和障碍
unordered_map<int, vector<PII > > X, Y;
cin >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
X[x].emplace_back(y, 1);
Y[y].emplace_back(x, 1);
}
cin >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
X[x].emplace_back(y, 0);
Y[y].emplace_back(x, 0);
}
//记录同一行/列能互相攻击到的两个列/行坐标
vector<TIII > boy, girl;
for (auto [x, vec]: X)
{
std::sort(vec.begin(), vec.end());
for (int i = 1; i < vec.size(); i++)
{
//y1 < y2
auto [y1, tag1] = vec[i - 1];
auto [y2, tag2] = vec[i];
if (tag1 && tag2)
{
if (y1 + 1 == y2) return (void) (cout << -1 << endl); //相邻无解
boy.emplace_back(x, y1, y2);//位于x行的y1列 和 y2列能互相攻击
}
}
}
for (auto [y, vec]: Y)
{
std::sort(vec.begin(), vec.end());
for (int i = 1; i < vec.size(); i++)
{
//x1 < x2
auto [x1, tag1] = vec[i - 1];
auto [x2, tag2] = vec[i];
if (tag1 && tag2)
{
if (x1 + 1 == x2) return (void) (cout << -1 << endl); //相邻无解
girl.emplace_back(y, x1, x2);//位于y列的x1行 和 x2行能互相攻击
}
}
}
vector adj(n, vector<int>());
n = boy.size(), m = girl.size();
//男孩选女孩
for (auto u = 0; u < n; u++)
{
auto [x, y1, y2] = boy[u];
for (auto v = 0; v < m; v++)
{
auto [y, x1, x2] = girl[v];
//若位于十字中心 双倍收益
if (x1 < x && x2 > x && y1 < y && y2 > y)
{
adj[u].emplace_back(v);
}
}
}
//跑最大匹配 即二分图的最小点覆盖
vector<int> vis(m), npy(m, -1);
function<bool(int)> dfs = [&](int u)
{
for (auto &v: adj[u])
{
if (vis[v]) continue;
vis[v] = true;
if (npy[v] == -1 || dfs(npy[v]))
{
npy[v] = u;
return true;
}
}
return false;
};
for (int u = 0; u < n; u++)
{
vector<int>(m).swap(vis);
dfs(u);
}
vector<PII > ans;//记录
vector<int> happy(n);//这个男孩有没有匹配到女朋友
for (int v = 0; v < m; v++)
{
if (npy[v] != -1)
{
happy[npy[v]] = true;
//男孩的行 女孩的列
ans.emplace_back(get<0>(boy[npy[v]]), get<0>(girl[v]));
}
else
{
auto [y, x1, x2] = girl[v]; //独立美丽
//放在中间即可
ans.emplace_back(x1 + 1, y);
}
}
for (int u = 0; u < n; u++)
{
if (!happy[u])
{
auto [x, y1, y2] = boy[u];
ans.emplace_back(x, y1 + 1);
}
}
cout << ans.size() << endl;
for (auto [x, y]: ans)
{
cout << x << " " << y << endl;
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << fixed << setprecision(2);
int Cases = 1;
cin >> Cases;
while (Cases--)
{
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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 4 6 2 3 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3752kb
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 29 38 20 12 34 18 5 12 6 20 26 34 50 16 10 16 15 0 1 16 10 0 1 43 22 5 42 44 1 3 1 13 33 10 44 45 0 5 8 1 21 15 29 26 27 41 44 4 1 32 9 0 0 0 0 6 23 10 24 46 35 34 23 44 12 11 29 21 0 3 31 17 20 30 43 25 0 -1 3 17 39 16 36 25 7 6 8 11 3 10 4 9 7 5 6 4 5 5
result:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3692kb
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 393 307 380 385 271 186 334 186 187 467 138 429 19 436 154 496 126 275 21 499 52 139 57 139 11 4 306 374 132 160 270 305 415 305 199 432 94 35 240 35 38 25 39 477 185 153 154 138 52 67 126 67 91 61 352 61 349 112 224 147 277 356 278 272 286 367 311 367 292 177 453 251 440 179 390 308 261 468 277 ...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3624kb
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 142917373 598813561 647691664 598813561 142917373 582720391 773363571 482933266 543529670 152471389 263974835 468188690 142917372 582720392 89287395 441913072 7 59832704 871951216 92745430 358274214 808969359 818037531 469117951 762966373 808969360 354711322 808969359 386523246 808969359 891229782...
result:
ok ok 20 cases (20 test cases)
Test #5:
score: 0
Accepted
time: 1ms
memory: 3800kb
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 724695106 464662104 730593611 362635470 495537855 699021890 554949791 699021890 496813081 421876106 556513262 421876106 561219908 421876106 702209411 421876106 469496530 461654555 469496530 154041437 730593611 810965373 814024114 802057256 702209411 468900569 469496529 438907614 471526869 438907...
result:
ok ok 2 cases (2 test cases)
Test #6:
score: 0
Accepted
time: 1ms
memory: 3704kb
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 554081387 850146190 529106065 789467242 946078033 789467242 585325539 381964778 412106896 998287777 412106896 977207026 412106896 108887129 365329222 141752547 412106895 141752547 365329221 211655411 412106895 211655411 585325540 211655411 365329221 657489855 412106895 657489855 585325540 657489...
result:
ok ok 2 cases (2 test cases)
Test #7:
score: 0
Accepted
time: 1ms
memory: 3880kb
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 867509363 839148357 757703055 909530095 679286177 322666885 708179173 956969180 314103357 11543659 752835605 213352628 340743563 288390629 509798823 292695446 25767121 610618164 561450008 934726175 867509363 374314271 509798823 741119775 658594226 784911403 145434751 34712108 622701955 191616432...
result:
ok ok 2 cases (2 test cases)
Test #8:
score: 0
Accepted
time: 1ms
memory: 3760kb
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 378192989 576579017 378192989 837331700 449924899 837331700 592684637 837331700 378192989 147499872 449924899 147499872 592684637 147499872 783332532 147499873 783332532 197547598 783332532 343857832 783332532 576579018 378192988 147499873 378192988 197547598 378192988 343857832 378192988 5765790...
result:
ok ok 20 cases (20 test cases)
Test #9:
score: 0
Accepted
time: 1ms
memory: 3692kb
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 590430725 987186358 649035661 942850783 538085060 887715271 461796409 868785127 906033133 790057179 317463343 662669999 312576627 949978130 255380788 624732370 270871854 556768926 331193631 551971959 140089445 535654097 479851779 522387718 237249112 488548916 513994713 457148969 194114590 438907...
result:
ok ok 2 cases (2 test cases)
Test #10:
score: 0
Accepted
time: 1ms
memory: 3720kb
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 782710197 901945895 514655989 861149655 279200011 646360861 523731402 243902652 496057717 490065400 538628510 293316179 446662965 383623456 754008138 390555088 2691940 984614319 30225808 984614319 39388077 984614319 55883390 984614319 77258753 984614319 106874918 984614319 144383293 984614319 14...
result:
ok ok 2 cases (2 test cases)
Test #11:
score: 0
Accepted
time: 1ms
memory: 3720kb
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 1005938 7 3412692 7 5764909 7 7897786 7 8061993 7 12801502 7 18529697 7 22574606 7 25203352 7 34574959 7 34998217 7 40928452 7 49792194 7 55962321 7 59632865 7 62353374 7 62611197 7 65346592 7 71459321 7 71550122 7 72215990 7 82584264 7 86119550 7 96204863 7 96940714 7 97693113 7 102067051 7 105...
result:
ok ok 2 cases (2 test cases)
Extra Test:
score: 0
Extra Test Passed