QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394192 | #5423. Perfect Matching | marher | WA | 1ms | 3648kb | C++14 | 1.5kb | 2024-04-20 10:01:06 | 2024-04-20 10:01:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
struct edge
{
int u,v,nxt,w,p;
}e[N];
int T,n,a[N],wa[N],wb[N],ma,mb,head[N],cnt=1,vis[N];
vector<pair<int,int>>ans;
void clear()
{
for(int i=1;i<=ma+mb;i++)head[i]=vis[i]=0;
cnt=1;vector<pair<int,int>>().swap(ans);
}
void add(int u,int v,int w)
{
// cout<<u<<' '<<v<<' '<<w<<'\n';
e[++cnt]=(edge){u,v,head[u],w,0};head[u]=cnt;
e[++cnt]=(edge){v,u,head[v],w,0};head[v]=cnt;
}
void ad(int x,int y)
{
ans.push_back(make_pair(e[x].w,e[y].w));
}
int dfs(int x,int fid)
{
// cout<<"DFS "<<x<<'\n';
int la=0;vis[x]=1;
for(int i=head[x];i;i=e[i].nxt)if(!e[i].p)
{
e[i].p=e[i^1].p=1;
int w=0;
if(!vis[e[i].v])w=dfs(e[i].v,i);
if(w)continue;
if(!la)la=i;else ad(la,i),la=0;
}
if(la)ad(la,fid);
// cout<<x<<' '<<fid<<' '<<la<<'\n';
return la!=0;
}
void sol()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)wa[i]=i-a[i],wb[i]=i+a[i];
sort(wa+1,wa+1+n);ma=unique(wa+1,wa+1+n)-wa-1;
sort(wb+1,wb+1+n);mb=unique(wb+1,wb+1+n)-wb-1;
for(int i=1;i<=n;i++)add(lower_bound(wa+1,wa+1+ma,i-a[i])-wa,lower_bound(wb+1,wb+1+mb,i+a[i])-wb+ma,i);
for(int i=1;i<=ma;i++)if(!vis[i]&&dfs(i,-1))
{
puts("NO");
return;
}
puts("YES");
for(auto x:ans)cout<<x.first<<' '<<x.second<<'\n';
}
main()
{
// freopen("in.txt","r",stdin);
cin>>T;
while(T--)sol(),clear();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3648kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
YES 6 3 5 2 4 1 YES 3 1 4 2 NO
result:
wrong answer Token parameter [name=s] equals to "YES", doesn't correspond to pattern "Yes|No" (test case 1)