QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91722 | #5423. Perfect Matching | Wolam | WA | 226ms | 11496kb | C++14 | 1.7kb | 2023-03-29 14:37:32 | 2023-03-29 14:37:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005],b[2][100005];
int vis[400005],head[200005],tot;
int h[400005];
struct ss{
int node,nxt;
}e[400005];
void add(int u,int v)
{
e[++tot].nxt=head[u];
e[tot].node=v;
head[u]=tot;
}
pair<int,int> ans[100005];
int len;
void dfs(int x,int fa)
{
// cerr<<x<<endl;
int now=0;
int f=0;
h[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].node;
if(vis[i])continue;
if(y==fa)
{
f=i;
continue;
}
if(!h[y])
dfs(y,x);
if(now)
{
ans[++len]=make_pair(now>>1,i>>1);
vis[i]=vis[i^1]=vis[now]=vis[now^1]=1;
now=0;
}
else now=i;
}
if(now&&f)
{
ans[++len]=make_pair(now>>1,f>>1);
vis[now]=vis[now^1]=vis[f]=vis[f^1]=1;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
// scanf("%d",&T);
while(T--)
{
cin>>n;
tot=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[0][i]=i+a[i];
b[1][i]=i-a[i];
}
sort(b[0]+1,b[0]+n+1);
sort(b[1]+1,b[1]+n+1);
b[0][0]=unique(b[0]+1,b[0]+n+1)-b[0]-1;
b[1][0]=unique(b[1]+1,b[1]+n+1)-b[1]-1;
for(int i=1;i<=b[0][0]+b[1][0];i++)
h[i]=head[i]=0;
for(int i=1;i<=n;i++)
{
int x=lower_bound(b[0]+1,b[0]+b[0][0]+1,a[i]+i)-b[0];
int y=lower_bound(b[1]+1,b[1]+b[1][0]+1,i-a[i])-b[1];
// cerr<<x<<" "<<y<<endl;
add(x,y+b[0][0]);add(y+b[0][0],x);
}
for(int i=1;i<=tot;i++)
vis[i]=0;
len=0;
for(int i=1;i<=b[0][0]+b[1][0];i++)
if(!h[i])dfs(i,0);
if(n==100000)cout<<tot<<" "<<len<<endl;
if(len==n/2)
{
cout<<"Yes\n";
for(int i=1;i<=len;i++)
cout<<ans[i].first<<" "<<ans[i].second<<'\n';
}
else cout<<"No\n";
}
}
/*
1
3 18 33
UDRLR
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7552kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 5 2 6 3 Yes 4 2 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 226ms
memory: 11496kb
input:
10 100000 0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...
output:
200001 58341 No 200001 58421 No 200001 58382 No 200001 58269 No 200001 58379 No 200001 58425 No 200001 58422 No 200001 58311 No 200001 58318 No 200001 58351 No
result:
wrong answer Token parameter [name=s] equals to "200001", doesn't correspond to pattern "Yes|No" (test case 1)