QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#180268#5423. Perfect MatchingZhou_JKWA 218ms17308kbC++231.8kb2023-09-15 17:34:442023-09-15 17:34:45

Judging History

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

  • [2023-09-15 17:34:45]
  • 评测
  • 测评结果:WA
  • 用时:218ms
  • 内存:17308kb
  • [2023-09-15 17:34:44]
  • 提交

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;
        if(vis[v]) continue;
        dfs(v,u,i);
    }
    for(auto [v,i]:G[u])
        if(i!=pre)
        {
            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++)
        if(a[i]!=0) G[pos[i-a[i]]].emplace_back(pos[i+a[i]],i),G[pos[i+a[i]]].emplace_back(pos[i-a[i]],i);
        else 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()
{
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout); 
    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: 8868kb

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
Wrong Answer
time: 218ms
memory: 17308kb

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:

Yes
1 4
2 40
3 31
5 7
6 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 99916
26 27
28 35
29 30
32 33
34 79
36 37
38 39
41 42
43 45
44 46
47 56
48 49
50 52
51 140
53 146
54 55
57 58
59 60
61 62
63 64
65 70
66 67
68 69
71 74
72 73
75 76
77 78
80 81
82 85
83 84
86 88
87 89
90 91
92 97
93 94
95 96
...

result:

wrong answer abs(3-31) != abs(a[3]-a[31]) (test case 1)