QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#604227#9412. Stop the Castleucup-team3474WA 1ms3948kbC++205.1kb2024-10-02 02:06:382024-10-02 02:06:39

Judging History

This is the latest submission verdict.

  • [2024-10-02 02:06:39]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3948kb
  • [2024-10-02 02:06:38]
  • 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[ii][i];
    }
    if(val1>0&&val2>0){
        // cout<<ri<<" "<<cj<<" "<<val1<<" "<<val2<<endl;
        add(val1,val2);
    } 
}


void __(){
    
    cin>>n;
    mpd.clear();
    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]){
            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;
            ans.push_back({u.first,v.second});
            mp[{u.first,v.second}]=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();
    for(int i=0;i<=214;i++) rid[i].clear(),cid[i].clear();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 3768kb

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

result:

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