QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610204#9412. Stop the CastleZariaWA 1ms3784kbC++176.4kb2024-10-04 15:14:572024-10-04 15:14:57

Judging History

This is the latest submission verdict.

  • [2024-10-04 15:14:57]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3784kb
  • [2024-10-04 15:14:57]
  • 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});
                    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});
                    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);
                    ss.insert({x,y});
                }
            }
        }
    }

    //找出最优方案
    //priority_queue<op> q;
    vector<PLL> re;
    for(int i=0;i<len;i++){
        if(!st[i]){
            bool flag=false;
            for(int j=h[i];~j;j=ne[j]){
                int jj=e[j];
                if(!st[jj]){
                    st[i]=st[jj]=true;
                    re.push_back({i,jj});
                    flag=true;
                    break;
                }
            }
            if(!flag){
                re.push_back({i,-1});
                st[i]=true;
            }
        }
    }

    //求点
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

result:

ok ok 21 cases (21 test cases)

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3632kb

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:

51
35 276
52 275
91 138
94 35
126 67
126 214
132 305
154 153
154 467
185 147
187 433
187 453
199 356
224 374
224 393
260 223
261 468
270 187
274 67
277 189
277 273
306 368
311 177
311 455
334 367
349 112
352 186
390 308
393 307
440 179
453 251
10 160
11 4
13 61
312 61
19 436
21 499
25 139
57 139
38 ...

result:

wrong answer Participant's answer is 51, but jury has better answer 46 (test case 1)