QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180308 | #5423. Perfect Matching | Zhou_JK | AC ✓ | 376ms | 38556kb | C++23 | 1.8kb | 2023-09-15 18:03:02 | 2023-09-15 18:03:02 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cassert>
#include<vector>
#include<unordered_map>
using namespace std;
const int N=100005;
const long long INF=4557430888798830399;
int n;
int a[N];
int tot;
vector<pair<long long,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]+INF)) pos[i+a[i]+INF]=++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]+INF],i),G[pos[i+a[i]+INF]].emplace_back(pos[i-a[i]],i);
match[0]=0;
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: 8536kb
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: 0
Accepted
time: 255ms
memory: 20668kb
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 100000 2 33 3 79 4 6 5 7 8 9 10 13 11 12 14 15 16 20 17 18 19 26 21 22 23 25 24 99915 27 28 29 31 30 99 32 34 35 59 36 37 38 99908 39 40 41 42 43 45 44 46 47 56 48 49 50 99920 51 52 53 248 54 55 57 58 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 80 75 76 77 78 81 82 83 84 85 89 86 88 87 97 90 ...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 8568kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 1 2 3 4 5 6 7 8 9 28 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 34 30 31 32 33 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 68 60 61 62 63 64 65 66 67 69 74 70 71 72 73 75 100 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 187ms
memory: 38556kb
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...
output:
Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 376ms
memory: 24076kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 1 4547 2 1932 3 24074 4 9 5 1492 6 140 7 1055 8 97 10 91206 11 449 12 2782 13 14 15 4917 16 7994 17 3227 18 1033 19 405 20 241 21 22355 22 24734 23 24 25 72 26 1088 27 99313 28 89504 29 33 30 97820 31 1158 32 44 34 163 35 82 36 730 37 11617 38 383 39 20594 40 105 41 54113 42 85 43 45 46 1832 47 ...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 169ms
memory: 8868kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 1 4 2 8 3 5 6 9 7 999 10 19 11 13 12 988 14 15 16 17 18 21 20 24 22 23 25 27 26 28 29 38 30 39 31 32 33 34 35 42 36 37 40 46 41 43 44 52 45 49 47 48 50 53 51 62 54 58 55 56 57 59 60 63 61 65 64 79 66 67 68 70 69 76 71 83 72 73 74 75 77 78 80 84 81 85 82 86 87 118 88 89 90 96 91...
result:
ok 1000 Cases (1000 test cases)