QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609845#9412. Stop the CastleKomorebie#WA 2ms3832kbC++177.1kb2024-10-04 14:13:332024-10-04 14:13:34

Judging History

This is the latest submission verdict.

  • [2024-10-04 14:13:34]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3832kb
  • [2024-10-04 14:13:33]
  • 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);
                    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
3
1 1 
1 3
1 5
0
*/

详细

Test #1:

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

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: 0
Accepted
time: 1ms
memory: 3520kb

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 15
20 26
0
1
16 10
0
1
43 22
5
1 3
33 10
42 44
1 13
44 45
0
5
27 41
44 4
21 15
29 26
8 1
1
32 9
0
0
0
0
6
12 11
23 44
24 46
29 21
23 10
35 34
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:

ok ok 21 cases (21 test cases)

Test #3:

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

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:

46
35 276
224 393
390 308
440 179
453 251
286 367
278 272
271 186
311 455
138 429
415 305
240 35
187 433
277 189
52 67
38 25
39 477
261 468
274 67
57 139
19 436
21 499
11 4
380 385
311 177
126 275
199 432
154 496
187 467
306 374
52 139
393 307
260 223
334 367
352 61
349 112
280 186
224 147
185 35
27...

result:

ok ok 2 cases (2 test cases)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

20
13
89287395 441913071
89287395 590314987
142917372 582720391
142917372 598813561
232930851 582720391
263974835 468188689
263974835 490702144
543529670 152471388
543529670 219371706
647691663 598813561
772865038 598813561
773363571 482933265
773363571 561453301
8
128947560 120560639
264980960 4742...

output:

8
89287395 441913072
263974835 468188690
142917373 598813561
142917373 582720391
647691664 598813561
773363571 482933266
142917372 582720392
543529670 152471389
7
808969359 386523246
808969359 891229782
469117951 762966373
59832704 871951216
92745430 358274214
808969360 354711322
808969359 818037531...

result:

ok ok 20 cases (20 test cases)

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 3624kb

input:

2
184
35763790 435860426
152681166 443483111
261932524 745277126
261932524 787982418
314305867 342102981
314305867 522593781
314305867 747023891
314305867 811404535
314305867 816914009
314305867 857896659
319901983 797458033
321347896 342102981
332550928 902179526
343207116 914408792
350635050 15515...

output:

160
261932524 745277127
314305867 522593782
350635050 155155062
673102149 351421769
702209412 342102981
716861004 342102981
730593612 342102981
712954987 342102981
673102149 356915105
638591122 342102981
673102150 342102981
611662527 342102981
620290597 342102981
496813081 751818165
673102149 342102...

result:

wrong answer Participant's answer is 137, but jury has better answer 136 (test case 2)