QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#813146#9412. Stop the CastleCirnoNineWA 1ms3816kbC++235.7kb2024-12-13 22:30:572024-12-13 22:30:58

Judging History

This is the latest submission verdict.

  • [2024-12-13 22:30:58]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3816kb
  • [2024-12-13 22:30:57]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define ll long long
#define pii pair<int,int>

struct Line{
    int x1,y1,x2,y2;
    int cnt = 0;
    int id;

    bool operator<(Line t) {
        return cnt<t.cnt;
    }
};

void solve() {
    int n;
    cin >> n;

    vector<pii> a,b;
    vector<int> vtX,vtY;
    map<int,int> mpX,mpY;
    for (int i = 0; i < n; i++) {
        int x,y;
        cin >> x >> y;
        vtX.push_back(x);
        vtY.push_back(y);
        a.push_back({x,y});
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x,y;
        cin >> x >> y;
        vtX.push_back(x);
        vtY.push_back(y);
        b.push_back({x,y});
    }

    sort(vtX.begin(),vtX.end());
    int szX = unique(vtX.begin(),vtX.end())-vtX.begin();
    for (int i = 0; i < szX; i++) mpX[vtX[i]] = i;
    sort(vtY.begin(),vtY.end());
    int szY = unique(vtY.begin(),vtY.end())-vtY.begin();
    for (int i = 0; i < szY; i++) mpY[vtY[i]] = i;

    vector<vector<int>> mp(szX,vector<int>(szY,0));
    
    for (auto [x,y] : a) {
        int x2 = mpX[x];
        int y2 = mpY[y];
        mp[x2][y2] = 1;
    }

    for (auto [x,y] : b) {
        int x2 = mpX[x];
        int y2 = mpY[y];
        mp[x2][y2] = 2;
    }

    vector<Line> vtL;
    
    for (int i = 0; i < szX; i++) {
        for (int j = 0; j < szY; j++) {
            if (mp[i][j] != 1) continue;
            for (int x = i+1; x < szX; x++) {
                if (mp[x][j] == 2) break;
                if (mp[x][j] == 1) {
                    Line line;
                    line.x1 = min(i,x);
                    line.x2 = max(i,x);
                    line.y1 = j;
                    line.y2 = j;
                    vtL.push_back(line);
                }
            }
            for (int y = j+1; y < szY; y++) {
                if (mp[i][y] == 2) break;
                if (mp[i][y] == 1) {
                    Line line;
                    line.x1 = i;
                    line.x2 = i;
                    line.y1 = min(j,y);
                    line.y2 = max(j,y);
                    vtL.push_back(line);
                }
            }
        }
    }
    
    vector<vector<int>> lines(vtL.size());
    vector<bool> check(n+9,1);

    for (int i = 0; i < vtL.size(); i++) {
        auto [x1,y1,x2,y2,s1,_] = vtL[i];
        vtL[i].id = i;
        for (int j = i+1; j < vtL.size(); j++) {
            auto [x3,y3,x4,y4,s2,__] = vtL[j];
            if (x1 == x2 && y3 == y4) {
                if (y1 < y3 && y3 < y2 && x3 < x1 && x1 < x4) {
                    vtL[i].cnt++;
                    vtL[j].cnt++;
                    lines[i].push_back(j);
                    lines[j].push_back(i);
                }
            }
            else if (y1 == y2 && x3 == x4) {
                if (y3 < y1 && y1 < y4 && x1 < x3 && x3 < x2) {
                    vtL[i].cnt++;
                    vtL[j].cnt++;
                    lines[i].push_back(j);
                    lines[j].push_back(i);
                }
            }
        }
    }

    vector<pii> ans;
    auto vtL2 = vtL;
    sort(vtL.begin(),vtL.end());
    for (auto line : vtL) {
        auto [x1,y1,x2,y2,s1,id] = line;
        // cerr << "line:\n";
        // cerr << vtX[x1] << " " << vtY[y1] << endl;
        // cerr << vtX[x2] << " " << vtY[y2] << endl;
        if (check[id] == 0) continue;
        if (s1 == 0) { //无重叠
            if (x1 == x2) {
                int ry1 = vtY[y1];
                int ry2 = vtY[y2];
                if (ry2 - ry1 == 1) {
                    cout << -1 << endl;
                    return;
                }
                ans.push_back({vtX[x1],ry1+1});
            }else {
                int rx1 = vtX[x1];
                int rx2 = vtX[x2];
                if (rx2 - rx1 == 1) {
                    cout << -1 << endl;
                    return;
                }
                ans.push_back({rx1+1,vtY[y1]});
            }
            check[id] = 0;
        }else {
            int minCnt = 1000,minID = -1;
            for (auto id2 : lines[id]) {
                if (check[id2] == 0) continue;
                if (vtL2[id2].cnt < minCnt) {
                    minCnt = vtL2[id2].cnt;
                    minID = id2;
                }
            }
            if (minID == -1) { //无重叠
                if (x1 == x2) {
                    int ry1 = vtY[y1];
                    int ry2 = vtY[y2];
                    if (ry2 - ry1 == 1) {
                        cout << -1 << endl;
                        return;
                    }
                    ans.push_back({vtX[x1],ry1+1});
                }else {
                    int rx1 = vtX[x1];
                    int rx2 = vtX[x2];
                    if (rx2 - rx1 == 1) {
                        cout << -1 << endl;
                        return;
                    }
                    ans.push_back({rx1+1,vtY[y1]});
                }
                check[id] = 0;
                continue;
            }

            //重叠
            auto [x3,y3,x4,y4,s2,id2] = vtL2[minID];
            if (x1 == x2 && y3 == y4) {
                ans.push_back({vtX[x1],vtY[y3]});
            }
            else if (y1 == y2 && x3 == x4) {
                ans.push_back({vtX[x3],vtY[y1]});
            }
            check[id] = 0;
            check[id2] = 0;
        } 
    }
    
    cout << ans.size() << endl;
    for (auto [x,y] : ans) {
        cout << x << " " << y << endl;
    }
} 

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

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

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: 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
12 11
23 44
24 46
29 21
23 10
23 10
35 34
0
3
20 30
31 17
43 25
0
-1
3
17 39
25 7
16 36
6
8 11
3 10
4 9
5 5
6 4
7 3

result:

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