QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604205#9412. Stop the Castleucup-team3474WA 1ms3756kbC++204.6kb2024-10-02 01:29:422024-10-02 01:29:42

Judging History

This is the latest submission verdict.

  • [2024-10-02 01:29:42]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3756kb
Show
  • [2024-10-02 01:29:42]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=314,M=N*N;





int h[N],ne[M],e[M],idx;
int match[N];
int n1,n2,m;
int n;
bool tf[M];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int x){
    
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(tf[j]==0){
            tf[j]=1;
            if(match[j]==0||find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}

PII d[N],dd[N];


vector<int> r[314],c[314];

bool check(int ii,int ri,int jj,int cj){
    // for(int i=0)
    // cout<<ii<<" "<<ri<<" "<<jj<<" "<<cj<<endl;
    bool flag1=0,flag2=0;
    // for(auto x:r[ii]) cout<<x<<" ";
    // cout<<endl;
    // for(auto x:c[jj]) cout<<x<<" ";
    // cout<<endl;
    for(int i=1;i<r[ii].size();i++){
        // cout<<r[ii][i-1]<<" "<<r[ii][i]<<endl;
        if(cj>=r[ii][i-1]&&cj<=r[ii][i]) flag1=1;
    }
    for(int i=1;i<c[jj].size();i++){
        if(ri>=c[jj][i-1]&&ri<=c[jj][i]) flag2=1;
    }
    return flag1&&flag2;
}


void __(){
    
    cin>>n;
    
    map<PII,int> mp;
    for(int i=1;i<=n;i++){
        cin>>d[i].first>>d[i].second;
        mp[d[i]]=0;
    }
    cin>>m;
    
    for(int i=1;i<=m;i++){
        cin>>dd[i].first>>dd[i].second;
        mp[dd[i]]=1;
    }
    
    memset(h,-1,sizeof h);
    
    idx=0;
    vector<int> row,col;
    map<int,int> mpr,mpc;
    row.push_back(-1e9);
    col.push_back(-1e9);
    for(int i=1;i<=n;i++){
        row.push_back(d[i].first);
        col.push_back(d[i].second);
    }
    sort(row.begin(),row.end());
    row.erase(unique(row.begin(),row.end()),row.end());
    for(int i=1;i<row.size();i++) mpr[row[i]]=i;
    sort(col.begin(),col.end());
    col.erase(unique(col.begin(),col.end()),col.end());
    for(int i=1;i<col.size();i++) mpc[col[i]]=i;

    
    for(int i=1;i<=n;i++){
        int t1=mpr[d[i].first],t2=mpc[d[i].second];
        r[t1].push_back(d[i].second);
        c[t2].push_back(d[i].first);
    }
    for(int i=1;i<=n;i++){
        sort(r[i].begin(),r[i].end());
        sort(c[i].begin(),c[i].end());
    }
    for(int i=1;i<row.size();i++){
        for(int j=1;j<col.size();j++){
            PII zb={row[i],col[j]};
            if(!mp.count(zb)){
                if(check(i,row[i],j,col[j])){
                    if(n>100)cout<<i<<" "<<j<<endl;
                    add(i,j);
                } 
            }
        }
    }
    
    n1=row.size()-1,n2=col.size()-1;
    
    // cout<<n1<<" "<<n2<<endl;
    memset(match,0,sizeof match);
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(tf,false,sizeof tf);
        // cout<<i<<endl;
        if(find(i)) res++;
        
    }
    
    // cout<<res<<endl;
    if(n>100){
        cout<<res<<endl;
        exit(0);
    }
    vector<PII> ans;
    // cout<<n1<<endl;
    for(int i=1;i<=n2;i++){
        // cout<<i<<" "<<match[i]<<endl;
        if(match[i]!=0){
            int u=match[i],v=i;
            // cout<<row[u]<<" "<<col[v]<<endl;
            ans.push_back({row[u],col[v]});
            mp[{row[u],col[v]}]=1;
            
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<r[i].size();j++){
            bool flag=0;
            if(r[i][j]==r[i][j-1]+1){
                cout<<-1<<"\n";
                return;
            }
            for(auto [x,y]:mp){
                // if(y==0) continue;
                if(x.first!=row[i]) continue;
                if(r[i][j-1]<x.second&&r[i][j]>x.second) flag=1;
            }
            if(!flag){
                ans.push_back({row[i],r[i][j-1]+1});
                mp[{row[i],r[i][j-1]+1}]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<c[i].size();j++){
            bool flag=0;
            if(c[i][j]==c[i][j-1]+1){
                cout<<-1<<"\n";
                return;
            }
            for(auto [x,y]:mp){
                // if(y==0) continue;
                if(x.second!=col[i]) continue;
                if(c[i][j-1]<x.first&&c[i][j]>x.first) flag=1;
            }
            if(!flag){
                ans.push_back({c[i][j-1]+1,col[i]});
                mp[{c[i][j-1]+1,col[i]}]=1;
            }
        }
    }



    cout<<ans.size()<<"\n";
    for(auto [x,y]:ans) cout<<x<<" "<<y<<"\n";
}

int main(){
    // ios::sync_with_stdio(0);
    int _;
    cin>>_;
    while(_--){
        __();
        
    for(int i=0;i<=214;i++) r[i].clear(),c[i].clear();
    }
}
源文件, 语言: C++20

详细

Test #1:

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

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: 0
Accepted
time: 1ms
memory: 3720kb

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
6
5 5
8 11
6 4
7 3
4 9
3 10

result:

ok ok 21 cases (21 test cases)

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3756kb

input:

2
200
7 52
9 160
10 4
12 61
18 436
19 430
20 499
24 139
25 416
29 53
33 153
35 275
35 310
37 25
38 477
39 349
42 120
44 158
45 330
49 486
50 204
51 67
52 138
52 305
56 139
63 132
66 4
67 327
70 484
71 67
72 308
74 218
76 479
81 139
82 90
86 201
87 335
91 35
91 220
92 496
94 29
94 436
96 359
97 299
1...

output:

22 42
22 48
22 51
22 88
36 19
36 22
36 41
36 48
36 51
38 11
38 19
38 22
38 41
38 48
38 51
38 88
38 97
49 19
49 22
49 41
49 48
49 51
49 88
51 11
51 19
51 22
51 41
51 48
51 51
51 88
51 97
61 41
61 48
61 51
61 88
61 97
61 121
61 149
61 162
72 11
72 19
72 22
72 41
72 46
72 48
72 51
73 149
79 41
79 46
79...

result:

wrong answer Duplicated position (51, 38) (test case 1)
English 繁體中文 简体中文

服务器时间: 2025-02-08 21:41:28 | 开源项目