QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691615#9412. Stop the Castle0x3fffffffWA 1ms3656kbC++203.8kb2024-10-31 12:15:412024-10-31 12:15:42

Judging History

This is the latest submission verdict.

  • [2024-10-31 12:15:42]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3656kb
  • [2024-10-31 12:15:41]
  • Submitted

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;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 >> 1,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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3656kb

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: -100
Wrong Answer
time: 1ms
memory: 3564kb

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
4
1 7
1 26
33 28
44 44
0
5
29 33
27 41
44 21
9 1
26 15
1
32 10
0
0
0
0
5
23 10
23 46
12 25
29 34
35 25
0
3
20 30
43 28
32 17
0
-1
3
25 9
16 39
12 36
6
8 11
7 5
6 5
5 5
6 10
6 9

result:

wrong answer Duplicated position (44, 44) (test case 7)