QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#609995 | #9412. Stop the Castle | AAA___# | WA | 1ms | 3612kb | C++20 | 5.2kb | 2024-10-04 14:40:02 | 2024-10-04 14:40:05 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)