QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611477#9412. Stop the CastleKomorebieWA 0ms3796kbC++176.2kb2024-10-04 21:08:572024-10-04 21:08:57

Judging History

This is the latest submission verdict.

  • [2024-10-04 21:08:57]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3796kb
  • [2024-10-04 21:08:57]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define PII pair<int, int>
#define pi acos(-1.0)
#define x first
#define y second

struct pair_hash {
    template <class T1, class T2> size_t operator()(const pair<T1, T2>& p) const
    {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  // 哈希组合
    }
};

struct seg {
    PII a, b;
    bool vertical() { return a.second == b.second; }
    bool horizontal() { return a.first == b.first; }
};

void solve()
{
    int n;
    cin >> n;
    vector<PII> a(n + 1);
    unordered_set<PII, pair_hash> vis;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        vis.insert({a[i].first, a[i].second});
    }
    int m;
    cin >> m;
    vector<PII> b(m + 1);
    vector<seg> s;
    for (int i = 1; i <= m; i++) {
        cin >> b[i].first >> b[i].second;
        vis.insert({b[i].first, b[i].second});
    }

    auto checkno = [&](PII a, PII b) {
        auto [x1, y1] = a;
        auto [x2, y2] = b;
        if (x1 == x2 && abs(y1 - y2) == 1) return true;
        if (y1 == y2 && abs(x1 - x2) == 1) return true;
        return false;
    };

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            auto [x1, y1] = a[i];
            auto [x2, y2] = a[j];
            bool have = false;
            if (x1 != x2 && y1 != y2) continue;
            if (checkno(a[i], a[j])) {
                cout << -1 << endl;
                return;
            }
            for (int k = 1; k <= m; k++) {
                auto [x3, y3] = b[k];
                if (x1 == x2) {
                    if (x3 == x1 && y3 >= min(y1, y2) && y3 <= max(y1, y2)) {
                        have = true;
                        break;
                    }
                }
                else {
                    if (y3 == y1 && x3 >= min(x1, x2) && x3 <= max(x1, x2)) {
                        have = true;
                        break;
                    }
                }
            }
            if (!have) {
                if (a[i].x < a[j].x || a[i].y < a[j].y)
                    s.push_back({a[i], a[j]});
                else
                    s.push_back({a[j], a[i]});
            }
        }
    }

    // cout << s.size() << endl;

    // for (int i = 0; i < s.size(); i++) {
    //     cerr << s[i].a.first << " " << s[i].a.second << " " << s[i].b.first << " " << s[i].b.second << "vertical:"<<s[i].vertical()<<endl;
    // }

    vector<int> ver, hor;

    for (int i = 0; i < s.size(); i++) {
        if (s[i].vertical())
            ver.push_back(i);
        else
            hor.push_back(i);
    }

    auto check_cross = [&](seg a, seg b) {
        return (a.a.x < b.a.x && a.b.x > b.a.x && a.a.y > b.a.y && a.a.y < b.b.y);
    };

    vector<vector<int>> G(s.size());

    for (int i = 0; i < s.size(); i++) {
        if (s[i].vertical()) {
            for (int j = 0; j < s.size(); j++) {
                if (s[j].horizontal()) {
                    if (check_cross(s[i], s[j])) G[i].push_back(j);
                }
            }
        }
    }


    // cerr << "G" << endl;
    // for (int i = 0; i < s.size(); i++) {
    //     for (int v : G[i]) {
    //         cerr << v << " ";
    //     }
    //     cerr << endl;
    // }
    // /*
    // 3
    // 2
    // null
    // null
    // */
    // cerr<<"endG"<<endl<<endl;


    vector<bool> st;
    vector<int> match(s.size(), -1);

    auto find = [&](auto find, int u) -> bool {
        for (int v : G[u]) {
            if (!st[v]) {
                st[v] = true;
                if (match[v] == -1 || find(find, match[v])) {
                    match[v] = u;
                    // cerr<<"u:"<<u<<endl;
                    // cerr << v << " " << match[v] << endl;
                    return true;
                }
            }
        }
        return false;
    };

    for (int v : ver) {
        st.assign(s.size(), false);
        find(find, v);
    }

    vector<PII> ans;
    vector<int> have_ans(s.size());

    auto get_cross = [&](seg a, seg b) -> PII {
        assert(a.horizontal());
        // cerr << "fuck0" << endl;
        vector<int> x, y;
        x.push_back(a.a.first), x.push_back(a.b.first), x.push_back(b.a.first);
        y.push_back(a.a.second), y.push_back(b.a.second), y.push_back(b.b.second);
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        return {x[1], y[1]};
        // PII res = {x[1], y[1]};
        // int axl = min(a.a.first, a.b.first), axh = max(a.a.first, a.b.first);
        // int byl = min(b.a.second, b.b.second), byh = max(b.a.second, b.b.second);
        // if (x[1] >= axl && x[1] <= axh && y[1] == a.a.second && x[1] == b.a.first && y[1] <= byh && y[1] >= byl) {
        //     return res;
        // }
    };
    // cerr << "match" << endl;
    // for (int i = 0; i < s.size(); i++) {
    //     cerr << match[i] << " \n"[i==s.size() - 1];
    // }

    for (int h : hor) {
        if (match[h] != -1) {
            ans.push_back(get_cross(s[h], s[match[h]]));
            have_ans[h] = have_ans[match[h]] = 1;
        }
    }

    // cout << ans.size() << endl;
    // for (int i = 0; i < ans.size(); i++) {
    //     cout << ans[i].first << " " << ans[i].second << endl;
    // }

    auto get_point = [&](seg a) -> PII {
        if (a.vertical()) {
            return {a.a.first + 1, a.a.second};
        }
        else {
            return {a.a.first, a.a.second + 1};
        }
    };

    for (int i = 0; i < s.size(); i++) {
        if (!have_ans[i]) ans.push_back(get_point(s[i]));
    }

    // for (int i = 0; i < s.size(); i++) {
    //     if (!st[i]) {
    //         ans.push_back(get_point(s[i]));
    //     }
    // }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

详细

Test #1:

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

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

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

result:

wrong answer Duplicated position (16, 10) (test case 2)