QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609995#9412. Stop the CastleAAA___#WA 1ms3612kbC++205.2kb2024-10-04 14:40:022024-10-04 14:40:05

Judging History

This is the latest submission verdict.

  • [2024-10-04 14:40:05]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3612kb
  • [2024-10-04 14:40:02]
  • 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>
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=500;
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);
    int ans=0;
    for(int i=1;i<=idx;i++){
        if(Two.dfs(i)){
            ans++;
        }
    }
    return ans;
}
struct node
{
    ll x,y;
    bool operator<(node&that){
        if(that.x==this->x){
            return this->y<that.y;
        }else{
            return this->x<that.x;
        }
    }
};
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(id);
    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);
}
int 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: 3612kb

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

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
4
44 44
1 3
1 13
33 10
0
5
27 41
29 26
44 4
8 1
21 15
1
32 9
0
0
0
0
5
12 10
29 34
23 46
23 10
35 5
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:

wrong answer Duplicated position (44, 44) (test case 7)