QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#610144#9412. Stop the CastleAAA___#WA 1ms3836kbC++175.0kb2024-10-04 15:02:372024-10-04 15:02:37

Judging History

This is the latest submission verdict.

  • [2024-10-04 15:02:37]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3836kb
  • [2024-10-04 15:02:37]
  • Submitted

answer

#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<array>
#include<functional>
#define int long long
using namespace std;
typedef long long ll;
ll highbit(ll x){
    ll ans=1;
    int num=0;
    while(x){
        x>>=1;
        ans<<=1;
        num++;
    }
    return num;
}
ll lowbit(ll x){
    return x&(-x);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a>b?b:a;
}
long long exgcd(ll a,ll b,ll&x,ll&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll d=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return d;
}
ll gcd(ll x,ll y)
{
    if(y==0)
        return x;
    return gcd(y,x%y);
}
const int maxn=1000;
vector<int> G[maxn];
int id;
int idx,idy;
struct TwoG_Match{
    int match[maxn];
    int v[maxn];
    void init(int n){
        for(int i=1;i<=n;i++){
            match[i]=0;
            v[i]=0;
        }
    }
    void clear(int n){
        for(int i=1;i<=n;i++){
            v[i]=0;
        }
    }
    bool dfs(int x){
        for(auto q:G[x]){
            if(v[q]){
                continue;
            }
            v[q]=1;
            if(!match[q]||dfs(match[q])){
                match[q]=x;
                return true;
            }
        }
        return false;
    }
}Two;
int cal(void){
    id=idx+idy;
    Two.init(id+10);
    int ans=0;
    for(int i=1;i<=idx;i++){
        if(Two.dfs(i)){
            ans++;
        }
    }
    return ans;
}
struct node
{
    ll x,y;
};
vector<node> pos1;
vector<node> pos2;
map<ll,set<ll> > mpx;
map<ll,set<ll> > mpy;
array<ll,3> X[maxn];
bool xv[maxn];
array<ll,3> Y[maxn];
bool yv[maxn];
void clear(int n){
    for(int i=1;i<=n;i++){
        G[i].clear();
        xv[i]=false;
        yv[i]=false;
    }
    Two.clear(n);
    mpx.clear();
    mpy.clear();
    id=idx=idy=0;
    pos1.clear();
    pos2.clear();
}
void T(void){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        node now;
        cin>>now.x>>now.y;
        mpx[now.x].insert(now.y);
        mpy[now.y].insert(now.x);
        pos1.push_back(now);
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        node now;
        cin>>now.x>>now.y;
        pos2.push_back(now);
    }
    for(auto x:mpx){
        int flag=0;
        ll pre;
        for(auto q:x.second){
            if(flag){
                if(pre+1==q){
                    cout<<-1<<endl;
                    clear(idx+idy);
                    return;
                }
                array<ll,3> now={pre,q,x.first};
                bool yes=true;
                for(auto tmp:pos2){
                    if(x.first==tmp.x&&tmp.y<q&&tmp.y>pre){
                        yes=false;
                        break;
                    }
                }
                if(yes){
                    X[++idx]=now;
                }
            }else{
                flag=1;
            }
            pre=q;
        }
    }
    for(auto y:mpy){
        int flag=0;
        ll pre;
        for(auto q:y.second){
            if(flag){
                if(pre+1==q){
                    cout<<-1<<endl;
                    clear(idx+idy);
                    return;
                }
                array<ll,3> now={pre,q,y.first};
                bool yes=true;
                for(auto tmp:pos2){
                    if(y.first==tmp.y&&tmp.x<q&&tmp.x>pre){
                        yes=false;
                        break;
                    }
                }
                if(yes){
                    Y[++idy]=now;
                }
            }else{
                flag=1;
            }
            pre=q;
        }
    }
    int x,y;
    x=y=0;
    for(int i=1;i<=idx;i++){
        array<ll,3> u=X[i];
        for(int j=1;j<=idy;j++){
            array<ll,3> v=Y[j];
            x=i;
            y=j;
            if(u[2]<v[1]&&u[2]>v[0]&&v[2]<u[1]&&v[2]>u[0]){
                G[x].push_back(y+idx);
                G[y+idx].push_back(x);
            }
        }
    }
    ll ans=cal();
    ll sum=id-ans;
    cout<<sum<<endl;
    for(int i=1+idx;i<=id;i++){
        if(Two.match[i]){
            cout<<X[Two.match[i]][2]<<" "<<Y[i-idx][2]<<endl;
            xv[Two.match[i]]=true;
            yv[i-idx]=true;
        }
    }
    for(int i=1;i<=idx;i++){
        if(!xv[i]){
            cout<<X[i][2]<<" "<<X[i][0]+1<<endl;
        }
    }
    for(int i=1;i<=idy;i++){
        if(!yv[i]){
            cout<<Y[i][0]+1<<" "<<Y[i][2]<<endl;
        }
    }
    clear(id);
}
signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    unsigned int t;
    //freopen("input.in","r",stdin);
    cin>>t;
    //t=1;
    while(t--){
        T();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3644kb

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

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 9
6 4
7 3
3 10
2 11

result:

ok ok 21 cases (21 test cases)

Test #3:

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

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:

49
94 35
91 61
349 61
126 67
311 112
132 138
52 139
185 147
154 153
199 160
334 186
126 275
224 305
393 307
270 356
154 374
187 467
35 276
187 433
224 393
260 223
261 468
274 67
277 189
277 273
306 368
311 455
352 36
390 308
440 179
453 251
11 4
38 25
240 35
52 67
57 139
292 177
271 186
278 272
415 ...

result:

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