QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604241#9412. Stop the Castleucup-team3474WA 2ms3944kbC++205.5kb2024-10-02 02:23:362024-10-02 02:23:38

Judging History

This is the latest submission verdict.

  • [2024-10-02 02:23:38]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3944kb
  • [2024-10-02 02:23:36]
  • 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];
vector<int> rid[314],cid[314];
PII mr[314],mc[314];
map<PII,int> mpd;

void check(int ii,int ri,int jj,int cj){
    // for(int i=0)
    // cout<<ii<<" "<<ri<<" "<<jj<<" "<<cj<<endl;
    int val1=-1,val2=-1;
    // 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]) val1=rid[ii][i];
    }
    for(int i=1;i<c[jj].size();i++){
        if(ri>c[jj][i-1]&&ri<c[jj][i]) val2=cid[jj][i];
    }
    
        // cout<<ri<<" "<<cj<<" "<<val1<<" "<<val2<<endl;
    if(val1>0&&val2>0){
        add(val1,val2);
    } 
}

bool rrr[N],ccc[N];

void __(){
    
    cin>>n;
    mpd.clear();
    memset(rrr,0,sizeof rrr);
    memset(ccc,0,sizeof ccc);
    map<PII,int> mp;
    for(int i=1;i<=n;i++){
        cin>>d[i].first>>d[i].second;
        mp[d[i]]=0;
        mpd[d[i]]=i;
    }
    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);
    }
    int ridx=0;
    for(int i=1;i<=n;i++){
        sort(r[i].begin(),r[i].end());
        sort(c[i].begin(),c[i].end());
    }
    // map<PII,int> mr,mc;
    for(int i=1;i<=n;i++){
        for(auto x:r[i]) {
            rid[i].push_back(mpd[{row[i],x}]);
        }
    }
    ridx=0;
    for(int i=1;i<=n;i++){
        for(auto x:c[i]){
            
            // cout<<col[i]<<" "<<x<<" "<<mpd[{x,col[i]}]<<endl;
            cid[i].push_back(mpd[{x,col[i]}]);
        } 
    }
    int cnt=0;
    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)){
                check(i,row[i],j,col[j]);
            }
        }
    }
    
    n1=n,n2=n;
    
    // cout<<n1<<" "<<n2<<endl;
    memset(match,0,sizeof match);
    int res=0;
    for(int i=1;i<=n;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<=n;i++){
        // cout<<i<<" "<<match[i]<<endl;
        if(match[i]!=0){
            PII u=d[match[i]],v=d[i];
            // cout<<row[u]<<" "<<col[v]<<endl;
            // cout<<u.first<<" "<<u.second<<" "<<v.first<<" "<<v.second<<endl;
            // if(mp.count({u.first,v.second})) continue;
            rrr[match[i]]=1,ccc[i]=1;
            ans.push_back({u.first,v.second});
            mp[{u.first,v.second}]=1;
            
        }
    }
    if(n>100){
        cout<<ans.size()<<endl;
        // exit(0);
    }
    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;
            }
            if(rrr[rid[i][j]]) continue;
            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;
            }
            if(ccc[cid[i][j]]) continue;
            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;
            }
        }
    }


if(n<=100){

    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();
    for(int i=0;i<=214;i++) rid[i].clear(),cid[i].clear();
    }
}

詳細信息

Test #1:

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

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
4 6
2 3
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3656kb

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

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:

20
24

result:

wrong output format Unexpected end of file - int32 expected (test case 1)