QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#610144 | #9412. Stop the Castle | AAA___# | WA | 1ms | 3836kb | C++17 | 5.0kb | 2024-10-04 15:02:37 | 2024-10-04 15:02:37 |
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>
#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)