QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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
*/
Details
Tip: Click on the bar to expand more detailed information
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)