QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#180247#5423. Perfect MatchingZhou_JKML 2ms8260kbC++231.6kb2023-09-15 17:13:072023-09-15 17:13:07

Judging History

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

  • [2023-09-15 17:13:07]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:8260kb
  • [2023-09-15 17:13:07]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<unordered_map>
using namespace std;
const int N=100005;
int n;
int a[N];
int tot;
vector<pair<int,int>>G[N*2];
int match[N];
bool vis[N*2];
void dfs(int u,int father,int pre)
{
    vis[u]=true;
    vector<int>edge;
    for(auto [v,i]:G[u])
    {
        if(v==father) continue;
        dfs(v,u,i);
        if(!match[i]) edge.emplace_back(i);
    }
    if(edge.size()%2==1) edge.emplace_back(pre);
    for(int i=0;i<(int)edge.size();i+=2)
        match[edge[i]]=edge[i+1],match[edge[i+1]]=edge[i];
    return;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    unordered_map<int,int>pos;
    tot=0;
    for(int i=1;i<=n;i++)
    {
        if(!pos.count(i-a[i])) pos[i-a[i]]=++tot;
        if(!pos.count(i+a[i])) pos[i+a[i]]=++tot;
    }
    for(int i=1;i<=tot;i++)
        G[i].clear(),vis[i]=false;
    for(int i=1;i<=n;i++)
        match[i]=0;
    for(int i=1;i<=n;i++)
        G[pos[i-a[i]]].emplace_back(pos[i+a[i]],i),G[pos[i+a[i]]].emplace_back(pos[i-a[i]],i);
    for(int i=1;i<=tot;i++)
        if(!vis[i])
        {
            dfs(i,0,0);
            if(match[0])
            {
                cout<<"No\n";
                return;
            }
        }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++)
        if(i<match[i]) cout<<i<<" "<<match[i]<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8260kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
1 4
2 5
3 6
Yes
1 3
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Memory 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...

output:


result: