QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180303 | #5423. Perfect Matching | Zhou_JK | WA | 361ms | 38556kb | C++23 | 2.1kb | 2023-09-15 17:57:30 | 2023-09-15 17:57:30 |
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)
{
// cerr<<"now"<<u<<" "<<edge[i]<<" "<<edge[i+1]<<"\n";
assert(edge[i]!=edge[i+1]);
if(edge[i+1]) assert(abs(edge[i]-edge[i+1])==abs(a[edge[i]]-a[edge[i+1]]));
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);//cerr<<pos[i-a[i]]<<" "<<pos[i+a[i]+INF]<<" "<<i<<"\n";
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: 8296kb
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: 244ms
memory: 20540kb
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: 8348kb
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: 190ms
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: 361ms
memory: 24204kb
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: -100
Wrong Answer
time: 141ms
memory: 9036kb
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 No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
wrong answer std outputs a valid answer while participant doesn't (test case 7)