QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691657#9412. Stop the Castle0x3fffffffAC ✓1ms3856kbC++203.8kb2024-10-31 12:29:362024-10-31 12:29:38

Judging History

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

  • [2024-10-31 12:29:38]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3856kb
  • [2024-10-31 12:29:36]
  • 提交

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