QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180268 | #5423. Perfect Matching | Zhou_JK | WA | 218ms | 17308kb | C++23 | 1.8kb | 2023-09-15 17:34:44 | 2023-09-15 17:34:45 |
Judging History
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)