QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604179#9412. Stop the Castleucup-team3474WA 1ms4200kbC++204.7kb2024-10-02 00:34:232024-10-02 00:34:23

Judging History

This is the latest submission verdict.

  • [2024-10-02 00:34:23]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4200kb
  • [2024-10-02 00:34:23]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=214,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];

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

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;
    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;

    
    memset(g,false,sizeof g);
    for(int i=1;i<=n;i++){
        int t1=mpr[d[i].first],t2=mpc[d[i].second];
        // cout<<t1<<" "<<t2<<endl;
        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());
        // unique(r[i].begin())
        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])){
                    // 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;
    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;
            
        }
    }

    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";
    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: 1ms
memory: 4200kb

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

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
8
12 20
26 39
23 10
23 44
29 21
35 5
30 34
24 46
0
3
20 30
43 25
31 17
0
-1
-1
-1

result:

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