QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394192#5423. Perfect MatchingmarherWA 1ms3648kbC++141.5kb2024-04-20 10:01:062024-04-20 10:01:07

Judging History

你现在查看的是最新测评结果

  • [2024-04-20 10:01:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3648kb
  • [2024-04-20 10:01:06]
  • 提交

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)