QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611861#9412. Stop the CastlepropaneWA 1ms3764kbC++203.7kb2024-10-04 23:19:302024-10-04 23:19:32

Judging History

This is the latest submission verdict.

  • [2024-10-04 23:19:32]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3764kb
  • [2024-10-04 23:19:30]
  • Submitted

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<array>
#include<algorithm>
using namespace std;
using LL = long long;

int match[1005];
bool v[1005];
vector<int> g[1005];

bool find(int x){
    for(auto j : g[x]){
        if (!v[j]){
            v[j] = true;
            if (match[j] == -1 or find(match[j])){
                match[j] = x;
                match[x] = j;
                return true;
            }
        }
    }
    return false;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        map<int, vector<int> > mp1, mp2;
        for(int i = 0; i < n; i++){
            int a, b;
            cin >> a >> b;
            mp1[a].push_back(b);
            mp2[b].push_back(a);
        }
        int m;
        cin >> m;
        map<int, vector<int> > mp3, mp4;
        for(int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            mp3[a].push_back(b);
            mp4[b].push_back(a);
        }
        
        auto norm = [&](map<int, vector<int> > &mp){
            for(auto &[x, v] : mp){
                sort(v.begin(), v.end());
            }
        };

        norm(mp1);
        norm(mp2);
        norm(mp3);
        norm(mp4);

        bool ok = true;

        auto solve = [&](map<int, vector<int> > &mp1, map<int, vector<int> > &mp3, vector<array<int, 3> > &p){
            auto check = [&](int x, int y1, int y2){
                if (!mp3.contains(x)) return false;
                auto &v = mp3[x];
                auto it = upper_bound(v.begin(), v.end(), y1);
                if (it != v.end() and *it < y2) return true;
                return false;
            };

            for(auto &[x, v] : mp1){
                for(int i = 0; i + 1 < v.size(); i++){
                    if (v[i] + 1 == v[i + 1]){
                        ok = false;
                    }
                    if (!check(x, v[i], v[i + 1])){
                        p.push_back({x, v[i], v[i + 1]});
                    }
                }
            }
        };

        vector<array<int, 3> > p1, p2;
        solve(mp1, mp3, p1);
        solve(mp2, mp4, p2);

        if (!ok){
            cout << -1 << '\n';
            continue;
        }

        const int s1 = p1.size(), s2 = p2.size();

        for(int i = 0; i < s1; i++){
            auto [x, y1, y2] = p1[i];
            for(int j = 0; j < s2; j++){
                auto [y, x1, x2] = p2[j];
                if (y > y1 and y < y2 and x > x1 and x < x2){
                    g[i].push_back(j + s1);
                }
            }
        }
        for(int i = 0; i < s1 + s2; i++){
            match[i] = -1;
        }
        for(int i = 0; i < s1; i++){
            for(int j = 0; j < s1 + s2; j++){
                v[j] = false;
            }
            find(i);
        }
        vector<pair<int, int> > ans;
        for(int i = 0; i < s1; i++){
            if (match[i] != -1){
                ans.push_back({p1[i][0], p2[match[i] - s1][0]});
            }
        }
        for(int i = 0; i < s1; i++){
            if (match[i] == -1){
                auto [x, y1, y2] = p1[i];
                ans.push_back({x, y1 + 1});
            }
        }
        for(int i = 0; i < s2; i++){
            if (match[i + s1] == -1){
                auto [y, x1, x2] = p2[i];
                ans.push_back({x1 + 1, y});
            }
        }
        cout << ans.size() << '\n';
        for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
    }

}

詳細信息

Test #1:

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

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: 3764kb

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
5
5 -902226764
6 9
7 5
8 10
2 11

result:

wrong answer Integer parameter [name=y_i] equals to -902226764, violates the range [1, 10^9] (test case 21)