QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609796#9412. Stop the CastleKomorebie#WA 1ms3632kbC++177.1kb2024-10-04 14:03:582024-10-04 14:03:59

Judging History

This is the latest submission verdict.

  • [2024-10-04 14:03:59]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3632kb
Show
  • [2024-10-04 14:03:58]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define PLL pair<ll,ll>
ll t,n,m;
struct node
{
    ll r,c;
    bool tag;//0为城堡 1为障碍物
};
struct seg
{
    node l,r;
};
struct pair_hash {
    template <class T1, class T2>
    size_t operator () (const pair<T1,T2> &p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2; // 哈希组合
    }
};
struct op{
    ll id,val;
    bool operator<(const op& a)const{
        return this->val > a.val;
    }
};

vector<node> row[510],col[510],res;
vector<seg> sg;
ll cnt_r,cnt_c;
unordered_map<ll,ll> hr,hc;
bool st[1010];
bool ok=true;
ll h[1010],ne[1010*2],e[1010*2],idx,di[1010];

bool cmp_r(node a,node b){
    return a.c<b.c;
}

bool cmp_c(node a,node b){
    return a.r<b.r;
}

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

node intersect(seg a,seg b){
    if(a.l.r==a.r.r&&b.l.r==b.r.r) return{0,0,0};
    if(a.l.c==a.r.c&&b.l.c==b.r.c) return{0,0,0};
    //a 列 b 行
    if(a.l.c==a.r.c&&b.l.r==b.r.r){
        a.l.r++,a.r.r--,b.l.c++,b.r.c--;
        if(a.l.r-a.r.r==1||b.l.c-b.r.c==1) return{0,0,0};
        if(a.l.c<b.l.c||a.l.c>b.r.c) return{0,0,0};
        if(b.l.r<a.l.r||b.l.r>a.r.r) return{0,0,0};
        return{b.l.r,a.l.c,0};
    }
    //a 行 b 列
    if(a.l.r==a.r.r&&b.l.c==b.r.c){
        a.l.c++,a.r.c--,b.l.r++,b.l.r--;
        if(b.l.r-b.r.r==1||a.l.c-a.r.c==1) return{0,0,0};
        if(b.l.c<a.l.c||b.l.c>a.r.c) return{0,0,0};
        if(a.l.r<b.l.r||a.l.r>b.r.r) return{0,0,0};
        return{a.l.r,b.l.c,0};
    }
    return{0,0,0};
}

void init(){
    //城堡
    cin>>n;
    for(int i=1;i<=n;i++){
        ll r,c;
        cin>>r>>c;
        //行
        if(!hr.count(r)){
            hr[r]=++cnt_r;
            row[hr[r]].push_back({r,c,0});
        }
        else{
            row[hr[r]].push_back({r,c,0});
        }

        //列
        if(!hc.count(c)){
            hc[c]=++cnt_c;
            col[hc[c]].push_back({r,c,0});
        }
        else{
            col[hc[c]].push_back({r,c,0});
        }
    }

    //障碍物
    cin>>m;
    for(int i=1;i<=m;i++){
        ll r,c;
        cin>>r>>c;
        //行
        if(!hr.count(r)){
            hr[r]=++cnt_r;
            row[hr[r]].push_back({r,c,1});
        }
        else{
            row[hr[r]].push_back({r,c,1});
        }

        //列
        if(!hc.count(c)){
            hc[c]=++cnt_c;
            col[hc[c]].push_back({r,c,1});
        }
        else{
            col[hc[c]].push_back({r,c,1});
        }
    }
    
    for(int i=1;i<=cnt_r;i++){
        sort(row[i].begin(),row[i].end(),cmp_r);
    }
    for(int i=1;i<=cnt_c;i++){
        sort(col[i].begin(),col[i].end(),cmp_c);
    }
}

void get_seg(){
    //行
    for(int i=1;i<=cnt_r;i++){
        bool flag=false;
        node pre={0,0,0};
        for(int j=0;j<row[i].size();j++){
            auto d=row[i][j];
            if(d.tag==0){
                if(flag){
                    sg.push_back({pre,d});
                }
                else{
                    flag=true;
                    pre=d;
                }
            }
            else{
                flag=false;
            }
        }
    }

    //列
    for(int i=1;i<=cnt_c;i++){
        bool flag=false;
        node pre={0,0,0};
        for(int j=0;j<col[i].size();j++){
            auto d=col[i][j];
            if(d.tag==0){
                if(flag){
                    sg.push_back({pre,d});
                }
                else{
                    flag=true;
                    pre=d;
                }
            }
            else{
                flag=false;
            }
        }
    }
}

void clear(){
    for(int i=1;i<=cnt_r;i++) row[i].clear();
    for(int i=1;i<=cnt_c;i++) col[i].clear();
    for(int i=1;i<=1000;i++) st[i]=false;
    sg.clear();
    hr.clear();
    hc.clear();
    cnt_c=cnt_r=0;
    res.clear();
    ok=true;
}

void get_res(){
    unordered_set<PLL,pair_hash> ss;
    ll len=sg.size();

    idx=0;
    for(int i=0;i<len;i++) h[i]=-1,di[i]=0,st[i]=0;

    //存图
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            if(i==j) continue;
            auto d=intersect(sg[i],sg[j]);
            if(d.r!=0||d.c!=0){
                ll x=i,y=j;
                if(x>y) swap(x,y);
                if(!ss.count({x,y})){
                    add(x,y),add(y,x);
                    di[x]++,di[y]++;
                    ss.insert({x,y});
                }
            }
        }
    }

    //找出最优方案
    priority_queue<op> q;
    vector<PLL> re;
    for(int i=0;i<len;i++) q.push({i,di[i]});
    while(q.size()){
        auto d=q.top();
        if(d.val==0){
            q.pop();
            re.push_back({d.id,-1});
        }
        else{
            if(st[d.id]){
                q.pop();
                continue;
            }
            ll u=-1;
            st[d.id]=true;
            for(int i=h[d.id];~i;i=ne[i]){
                int j=e[i];
                if(!st[j]){
                    st[j]=true;
                    u=j;
                    di[d.id]--,di[j]--;
                    break;
                }
            }
            for(int i=h[d.id];~i;i=ne[i]){
                int j=e[i];
                if(!st[j]){
                    di[j]--;
                }
            }
            if(u!=-1){
                for(int i=h[u];~i;i=ne[i]){
                    int j=e[i];
                    if(!st[j]){
                        di[j]--,di[u]--;
                        break;
                    }
                }
            }
            re.push_back({d.id,u});
            q.pop();
        }
    }

    //求点
    for(int i=0;i<re.size();i++){
        auto dd=re[i];
        if(dd.second==-1){
            auto d=sg[dd.first];
            //为行
            if(d.l.r==d.r.r){
                if(d.l.c+1==d.r.c){
                    ok=false;
                }
                else{
                    res.push_back({d.l.r,d.l.c+1,0});
                }
            }
            //为列
            if(d.l.c==d.r.c){
                if(d.l.r+1==d.r.r){
                    ok=false;
                }
                else{
                    res.push_back({d.l.r+1,d.l.c,0});
                }
            }
        }
        else{
            auto d=intersect(sg[dd.first],sg[dd.second]);
            res.push_back({d.r,d.c,0});
        }
    }
}

int main(){
    cin>>t;
    while(t--){
        init();//读入数据并排序
        get_seg();//将数据处理成需要隔断的线段
        get_res();//得到答案
        if(ok){
            cout<<res.size()<<endl;
            for(auto d:res){
                cout<<d.r<<' '<<d.c<<endl;
            }
        }
        else{
            cout<<-1<<endl;
        }
        clear();
    }
    return 0;
}
/*
1
12
3 1
3 9
1 3
1 5
1 7
5 1
5 9
7 1
7 9
9 3
9 5
9 7
0*/
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

result:

wrong answer Duplicated position (16, 10) (test case 2)
English 繁體中文 简体中文

Server Time: 2025-02-08 19:12:05 | OpenSource Project