QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180247 | #5423. Perfect Matching | Zhou_JK | ML | 2ms | 8260kb | C++23 | 1.6kb | 2023-09-15 17:13:07 | 2023-09-15 17:13:07 |
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;
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...