QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603813#9412. Stop the Castleucup-team3474WA 2ms4652kbC++205.3kb2024-10-01 19:28:122024-10-01 19:28:12

Judging History

This is the latest submission verdict.

  • [2024-10-01 19:28:12]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 4652kb
  • [2024-10-01 19:28:12]
  • Submitted

answer

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





int h[M],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){
    // cout<<x<<endl;
    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];

int g[214][214];
bool rowtf[214],coltf[214];

int lr[214],lc[214],rr[214],rc[214];
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;
    }
    // cout<<114514<<endl;
    memset(lr,0x3f,sizeof lr);
    memset(rr,-0x3f,sizeof rr);
    memset(lc,0x3f,sizeof lc);
    memset(rc,-0x3f,sizeof rc);
    
    memset(h,-1,sizeof h);
    
    idx=0;
    memset(rowtf,0,sizeof rowtf);
    memset(coltf,0,sizeof coltf);
    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 r1=mpr[d[i].first],c1=mpc[d[i].second];
        lr[r1]=min(lr[r1],c1),rr[r1]=max(rr[r1],c1);
        lc[c1]=min(lc[c1],r1),rc[c1]=max(rc[c1],r1);

    }


    memset(g,false,sizeof g);
    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(mp[zb]==1){
                    // cout<<"--"<<i<<" "<<j<<endl;
                    rowtf[i]=1;coltf[j]=1;
                }
            }else{
                // cout<<i<<" "<<j<<" "<<row[i]<<" "<<col[j]<<endl;
                g[i][j]=1;
            }
        }
    }
    
    n1=row.size()-1,n2=col.size()-1;
    for(int i=1;i<=n1;i++){
        for(int j=1;j<=n2;j++){

            if(rowtf[i]||coltf[j]||!g[i][j]) continue;
            if(j>=lr[i]&&j<=rr[i]&&i>=lc[j]&&i<=rc[j]){
                // cout<<i<<" "<<j<<" "<<row[i]<<" "<<col[j]<<endl;
                add(i,j);
            }
            // cout<<i<<" "<<j<<endl;
            
        }
    }
    // 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<<14<<endl;
    vector<PII> ans;
    // cout<<n1<<endl;
    for(int i=1;i<=n1;i++){
        // cout<<i<<" ";
        if(match[i]!=0){
            int u=i,v=match[i];
            // cout<<u<<" "<<v<<endl;
            ans.push_back({row[u],col[v]});
            mp[{row[u],col[v]}]=1;
            rowtf[u]=1,coltf[v]=1;
        }
    }
    // cout<<endl;
    for(int i=1;i<=n1;i++){
        if(rowtf[i]) continue;
        int x=row[i],y=0x3f3f3f3f,mx=-0x3f3f3f3f;
        // cout<<i<<endl;
        bool flag=0;
        y=col[lr[i]],mx=col[rr[i]];

        if(mx==y) flag=1;
        // cout<<y<<" "<<mx<<endl;
        for(auto [xx,yy]:mp){
            if(yy==1&&xx.first==x){
                if(xx.second>y&&xx.second<mx) flag=1;
            }
        }
        if(flag) continue;
        while(y<=mx){
            if(!mp.count({x,y})){
                ans.push_back({x,y});
                flag=1;
                break;
            }

            y++;
        }
        // cout<<flag<<endl;
        if(!flag){
            cout<<-1<<"\n";
            return;
        }

    }
    // cout<<114514<<endl;
    // cout<<n2<<endl;
    for(int i=1;i<=n2;i++){
        if(coltf[i]) continue;
        int x=col[i],y=0x3f3f3f3f,mx=-0x3f3f3f3f;
        bool flag=0;
        // cout<<i<<" "<<lc[i]<<" "<<rc[i]<<endl;
        y=row[lc[i]],mx=row[rc[i]];
        // cout<<"--"<<y<<" "<<mx<<endl;
        if(mx==y) flag=1;
        for(auto [xx,yy]:mp){
            // if(yy==1) cout<<xx.first<<" "<<xx.second<<endl;
            if(yy==1&&xx.second==x){
                // cout<<xx.first<<" "<<xx.second<<endl;
                if(xx.first>y&&xx.first<mx) flag=1;
            }
        }
        // cout<<endl;
        // cout<<flag<<endl;
        if(flag) continue;
        while(y<=mx){
            // cout<<y<<" "<<x<<endl;
            if(!mp.count({y,x})){
                ans.push_back({y,x});
                flag=1;
                break;
            }
            y++;
        }
        if(!flag){
            cout<<-1<<"\n";
            return;
        }

    }
    cout<<ans.size()<<"\n";
    for(auto [x,y]:ans) cout<<x<<" "<<y<<"\n";
    // for(int i=0;i<214;i++) r[i].clear(),c[i].clear();
}

int main(){
    // ios::sync_with_stdio(0);
    int _;
    cin>>_;
    while(_--){
        __();
    }
}

詳細信息

Test #1:

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

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: 2ms
memory: 4556kb

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

result:

wrong answer There are still 1 pairs of castles which can attack each other (test case 2)