QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665342#9412. Stop the CastleRUOHUIAC ✓1ms3880kbC++203.9kb2024-10-22 11:33:552024-10-22 11:33:56

Judging History

你现在查看的是最新测评结果

  • [2024-10-22 11:33:56]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3880kb
  • [2024-10-22 11:33:55]
  • 提交

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