QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#795001#9412. Stop the CastleXiaoretaWWA 1ms3768kbC++204.6kb2024-11-30 17:23:552024-11-30 17:23:56

Judging History

This is the latest submission verdict.

  • [2024-11-30 17:23:56]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3768kb
  • [2024-11-30 17:23:55]
  • Submitted

answer

#include <bits/stdc++.h>

#define debug(...) 42;
#ifdef LOCAL
#include "debug.h"
#endif

using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }

void solve(){
    int n; cin >> n;
    map<int, vector<int>> rowA, colA;
    map<int, vector<int>> rowB, colB;

    for(int i = 0; i < n; i++){
        int r, c; cin >> r >> c;
        rowA[r].push_back(c);
        colA[c].push_back(r);
    }

    map<pii, int> ob;
    int m; cin >> m;
    for(int i = 0; i < m; i++){
        int r, c; cin >> r >> c;
        rowB[r].push_back(c);
        colB[c].push_back(r);
        ob[{r, c}] = 1;
    }

    int id = 0, L = 0;
    map<int, int> to;
    map<pii, int> belx;
    map<pii, int> bely;
    for(auto&[r, posx]: rowA){
        sort(all(posx));
        int num = posx.size();
        for(int i = 0; i < num - 1; i++){
            to[++id] = r;
            belx[{posx[i], posx[i + 1]}] = id;
        }
    }

    L = id;
    
    for(auto&[c, posy]: colA){
        sort(all(posy));
        int num = posy.size();
        for(int i = 0; i < num - 1; i++){
            to[++id] = c;
            bely[{posy[i], posy[i + 1]}] = id;
        }
    }

    vector<vector<int>> adj(L + 1);

    for(auto&[r, posx]: rowA){
        int numx = posx.size();
        for(int i = 0; i < numx - 1; i++){
            if(posx[i] + 1 == posx[i + 1]){
                cout << -1 << '\n';
                return;
            }
            auto it = upper_bound(all(rowB[r]), posx[i]);
            int posr = posx[i + 1];
            if(it == rowB[r].end() or *it > posr){
                for(auto&[c, posy]: colA){
                    int numy = posy.size();
                    for(int j = 0; j < numy - 1; j++){
                        if(posy[j] + 1 == posy[j + 1]){
                            cout << -1 << '\n';
                            return;
                        }
                        auto it2 = upper_bound(all(colB[c]), posy[j]);
                        int posr2 = posy[j + 1];
                        if(it2 == colB[c].end() or *it2 > posr2){
                            if(!ob.count({r, c}) and posy[j] < r and posy[j + 1] > r and posx[i] < c and posx[i + 1] > c){
                                int u = belx[{posx[i], posx[i + 1]}];
                                int v = bely[{posy[j], posy[j + 1]}];
                                assert(u < v);
                                adj[u].push_back(v);
                            }
                        }
                    }
                }
            }
        }
    }

    vector<int> st(id + 1), match(id + 1);
    function<bool(int)> find = [&](int u){
        for(int v: adj[u]){
            if(!st[v]){
                st[v] = true;
                if(match[v] == 0 or find(match[v])){
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    };

    for(int i = 1; i <= L; i++){
        st.assign(id + 1, false);
        find(i);
    }

    vector<pii> ans;
    for(int u = L + 1; u <= id; u++){
        if(match[u]){
            int r = to[match[u]];
            int c = to[u];
            rowB[r].push_back(c);
            colB[c].push_back(r);
            ans.push_back({r, c});
        }
    }

    // debug(ans);

    for(auto&[_, vec]: rowB){
        sort(all(vec));
    }
    for(auto&[_, vec]: colB){
        sort(all(vec));
    }

    for(auto&[r, vec]: rowA){
        int num = vec.size();
        for(int i = 0; i < num - 1; i++){
            auto it = upper_bound(all(rowB[r]), vec[i]);
            int posr = vec[i + 1];
            if(it == rowB[r].end() or *it > posr){
                ans.push_back({r, vec[i] + 1});
            }
        }
    }

    for(auto&[c, vec]: colA){
        int num = vec.size();
        for(int i = 0; i < num - 1; i++){
            auto it = upper_bound(all(colB[c]), vec[i]);
            int posr = vec[i + 1];
            if(it == colB[c].end() or *it > posr){
                ans.push_back({vec[i] + 1, c});
            }
        }
    }

    cout << ans.size() << '\n';
    for(auto[x, y]: ans){
        cout << x << ' ' << y << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3496kb

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: 1ms
memory: 3768kb

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
20 12
34 18
29 38
5
16 10
16 15
12 6
20 26
34 50
0
1
16 10
0
1
43 22
5
1 3
1 13
33 10
44 45
42 44
0
5
27 41
29 26
44 4
8 1
21 15
1
32 9
0
0
0
0
6
23 10
35 34
12 11
23 44
29 21
24 46
0
3
20 30
43 25
31 17
0
-1
3
16 36
25 7
17 39
6
5 5
8 9
6 4
7 3
3 10
2 11

result:

ok ok 21 cases (21 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3712kb

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
224 35
94 61
349 61
91 67
393 112
132 138
52 139
185 147
154 153
126 160
311 177
352 186
126 275
277 305
270 356
334 367
306 374
199 432
187 467
154 496
35 276
187 433
224 393
260 223
261 468
274 67
277 189
311 455
390 308
440 179
453 251
11 4
38 25
240 35
52 67
57 139
271 186
278 272
415 305
391...

result:

ok ok 2 cases (2 test cases)

Test #4:

score: 0
Accepted
time: 1ms
memory: 3616kb

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
89287395 441913072
142917372 582720392
263974835 468188690
543529670 152471389
773363571 482933266
142917373 582720391
142917373 598813561
647691664 598813561
7
808969359 818037531
808969359 386523246
808969359 891229782
808969360 354711322
92745430 358274214
469117951 762966373
59832704 871951216...

result:

ok ok 20 cases (20 test cases)

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3680kb

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
469496529 159320601
702209411 328140561
407380694 342102981
496813081 342102981
593934227 357262498
702209411 362635470
554949791 421876106
673102149 421876106
350635050 435860426
469496529 438907614
561219907 438907614
314305867 443483111
712954986 449645826
495537855 461654555
702209411 468900...

result:

wrong answer Participant's answer is 141, but jury has better answer 136 (test case 2)