QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#609557 | #9412. Stop the Castle | UESTC_DECAYALI# | WA | 0ms | 3800kb | C++20 | 3.2kb | 2024-10-04 13:25:50 | 2024-10-04 13:26:00 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
const int N=205;
int t,n,m,mat[N],vis[N],ok[N]; pair <int,int> c[N],o[N]; vector <int> v[N];
inline bool find(CI now,CI idx)
{
for (auto to:v[now]) if (vis[to]!=idx)
{
vis[to]=idx;
if (mat[to]==-1||find(mat[to],idx))
return mat[to]=now,1;
}
return 0;
}
int main()
{
// freopen("H.in","r",stdin);
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n);
for (RI i=1;i<=n;++i)
scanf("%d%d",&c[i].fi,&c[i].se);
scanf("%d",&m);
for (RI i=1;i<=m;++i)
scanf("%d%d",&o[i].fi,&o[i].se);
vector <pair <int,int>> L,R; bool flag=1;
for (RI i=1;i<=n;++i) for (RI j=i+1;j<=n;++j)
{
if (c[i].fi!=c[j].fi) continue;
int l=c[i].se,r=c[j].se;
if (l>r) swap(l,r);
if (l+1==r) flag=0;
bool sign=1;
for (RI k=1;k<=m;++k)
if (o[k].fi==c[i].fi&&l<o[k].se&&o[k].se<r) sign=0;
if (sign) L.push_back({i,j});
}
for (RI i=1;i<=n;++i) for (RI j=i+1;j<=n;++j)
{
if (c[i].se!=c[j].se) continue;
int l=c[i].fi,r=c[j].fi;
if (l>r) swap(l,r);
if (l+1==r) flag=0;
bool sign=1;
for (RI k=1;k<=m;++k)
if (o[k].se==c[i].se&&l<o[k].fi&&o[k].fi<r) sign=0;
if (sign) R.push_back({i,j});
}
if (!flag) { puts("-1"); continue; }
for (RI i=0;i<L.size();++i) v[i].clear();
// for (auto [x,y]:L) printf("L:(%d,%d)\n",x,y);
// for (auto [x,y]:R) printf("R:(%d,%d)\n",x,y);
for (RI i=0;i<L.size();++i)
for (RI j=0;j<R.size();++j)
{
int X=c[L[i].fi].fi,Y=c[R[j].fi].se;
int xl=c[R[j].fi].fi,xr=c[R[j].se].fi;
int yl=c[L[i].fi].se,yr=c[L[i].se].se;
if (xl>xr) swap(xl,xr);
if (yl>yr) swap(yl,yr);
if (X<=xl||X>=xr||Y<=yl||Y>=yr) continue;
v[i].push_back(j);
}
memset(vis,-1,sizeof(vis));
memset(ok,-1,sizeof(ok));
memset(mat,-1,sizeof(mat));
for (RI i=0;i<L.size();++i) find(i,i);
vector <pair <int,int>> ans;
for (RI i=0;i<R.size();++i)
if (mat[i]!=-1)
{
int u=mat[i],v=i; ok[u]=1;
int X=c[L[u].fi].fi,Y=c[R[v].fi].se;
ans.push_back({X,Y});
}
for (RI i=0;i<L.size();++i)
if (ok[i]==-1)
{
auto [u,v]=L[i];
int l=c[u].se,r=c[v].se;
if (l>r) swap(l,r);
ans.push_back({c[u].fi,l+1});
}
for (RI i=0;i<R.size();++i)
if (mat[i]==-1)
{
auto [u,v]=R[i];
int l=c[u].fi,r=c[v].fi;
if (l>r) swap(l,r);
ans.push_back({l+1,c[u].se});
}
printf("%d\n",(int)ans.size());
for (auto [x,y]:ans) printf("%d %d\n",x,y);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
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: 0ms
memory: 3776kb
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 6 16 10 16 10 16 15 12 6 20 26 34 50 0 1 16 10 0 1 43 22 6 1 3 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 7 23 10 35 34 12 11 23 10 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:
wrong answer Duplicated position (16, 10) (test case 2)