QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#612586#9412. Stop the CastlewlhWA 0ms3800kbC++174.0kb2024-10-05 12:09:152024-10-05 12:09:17

Judging History

This is the latest submission verdict.

  • [2024-10-05 12:09:17]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3800kb
  • [2024-10-05 12:09:15]
  • Submitted

answer

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

#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

#define int long long
typedef pair<int,int> pr;
#define pb(x) push_back(x)
#define all(a) a.begin(),a.end()
#define fi first
#define se second

const int N = 1e6+10;
string YES="YES",Yes="Yes",yes="yes",NO="NO",No="No",no="no";
const int mod=998244353,inf=1e15;
int dx[]={0,0,-1,0,1},dy[]={0,-1,0,1,0};

struct nb{
    int x, y;
};

void shuchu(nb w){
    cout << w.x << ' ' << w.y << ' ';
}



void solve()
{
    int n, m;
    cin >> n;
    vector<nb>a(n + 1);
    for(int i = 1; i <= n; i ++){
        cin >> a[i].x >> a[i].y;
    }
    cin >> m;
    vector<nb>b(m + 1), bx, by;
    for(int i = 1; i <= m; i ++){
        cin >> b[i].x >> b[i].y;
    }
    for(int i = 1; i <= n; i ++) b.push_back(a[i]);

    vector<array<nb, 2>>vx, vy;
    vector<nb>ans;
    for(int i = 1; i <= n; i ++){
        for(int j = i + 1; j <= n; j ++){
            if(a[i].x == a[j].x){
                int f = 1;
                for(int k = 1; k <= n + m; k ++) if(b[k].x == a[i].x && min(a[i].y, a[j].y) < b[k].y && b[k].y < max(a[i].y, a[j].y)){
                    f = 0; break;
                }
                if(f == 0) continue;
                if(a[i].y + 1 == a[j].y || a[j].y + 1 == a[i].y){
                    cout << -1 << endl;
                    return ;
                }
                if(a[i].y < a[j].y) vx.push_back({a[i], a[j]});
                else vx.push_back({a[j], a[i]});
            }
            else if(a[i].y == a[j].y){
                int f = 1;
                for(int k = 1; k <= n + m; k ++) if(b[k].y == a[i].y && min(a[i].x, a[j].x) < b[k].x && b[k].x < max(a[i].x, a[j].x)){
                    f = 0; break;
                }
                if(f == 0) continue;
                if(a[i].x + 1 == a[j].x || a[j].x + 1 == a[i].x){
                    cout << -1 << endl;
                    return ;
                }
                if(a[i].x < a[j].x) vy.push_back({a[i], a[j]});
                else vy.push_back({a[j], a[i]});
            }
        }
    }
    // for(auto [x, y] : vx){
    //     shuchu(x), shuchu(y);
    //     cout << endl;
    // }
    // cout << endl;
    // for(auto [x, y] : vy){
    //     shuchu(x), shuchu(y);
    //     cout << endl;
    // }

    int nx = vx.size(), ny = vy.size();
    vector<vector<int>> vt(nx + 1);
    for(int i = 0; i < nx ; i ++){
        auto [x1, x2] = vx[i];
        for(int j = 0; j < ny; j ++){
            auto [y1, y2] = vy[j];
            if(y1.x < x1.x && x1.x < y2.x && x1.y < y1.y && y1.y < x2.y){
                vt[i].push_back(j);
            }
        }
    }

    vector<int>vis(nx + 1), match(ny + 1, -1);
    auto dfs = [&](auto&& dfs, int u) -> int{
        for(auto v:vt[u]){
            if(!vis[v]){
                vis[v] = 1;
                if(match[v] == -1 || dfs(dfs, match[v])){
                    match[v] = u;
                    return 1;
                }
            }
        }
        return 1;
    };
    for(int i = 0; i < nx; i ++){
        for(int j = 0; j < ny; j ++) vis[j] = 0;
        dfs(dfs, i);
    }
    // for(int j = 0; j < ny; j ++) cout << match[j] << ' ';
    // cout << endl;

    vector<int>visx(nx);
    for(int v = 0; v < ny; v ++){
        auto [y1, y2] = vy[v];
        if(match[v] != -1){
            int u = match[v];
            auto [x1, x2] = vx[u];
            ans.push_back({x1.x, y1.y});
            visx[u] = 1;
        }
        else{
            ans.push_back({y1.x + 1, y1.y});
        }
    }
    for(int i = 0; i < nx; i ++){
        if(!visx[i]){
            auto [x1, x2] = vx[i];
            ans.push_back({x1.x, x1.y + 1});
        }
    }
    cout << ans.size() << endl;
    for(auto [x, y] : ans){
        cout << x << ' ' << y << endl;
    }
}

signed main()
{
    ios;
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

詳細信息

Test #1:

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

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: 0ms
memory: 3800kb

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

result:

wrong answer Participant's answer is 7, but jury has better answer 6 (test case 21)