QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91707 | #5423. Perfect Matching | Wolam | TL | 2ms | 11632kb | C++14 | 1.6kb | 2023-03-29 14:02:54 | 2023-03-29 14:02:55 |
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;
}
else now=i;
}
if(now&&f)
{
ans[++len]=make_pair(now>>1,f>>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);
//cerr<<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: 2ms
memory: 11632kb
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
Time Limit Exceeded
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...