QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178338 | #5423. Perfect Matching | dsakhdkas | WA | 597ms | 12800kb | C++14 | 1.8kb | 2023-09-13 21:19:33 | 2023-09-13 21:19:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
vector< pair<int,int> > ans;
int T,n,a[100010],b[200010],Link[200010],dfn[200010],t,tot,sum;
bool vis[200010];
struct edge
{
int v,nex,id;
}e[200010];
void Insert(int x,int y,int z)
{
e[++t].nex=Link[x];e[t].v=y;Link[x]=t;e[t].id=z;return ;
}
void dfs(int now,int las)
{
dfn[now]=++tot;vis[now]=false;
vector <int> V;
for (int i=Link[now];i;i=e[i].nex) {
if (i==(las^1)) continue;
if (!dfn[e[i].v]) {
dfs(e[i].v,i);
sum++;
if (!vis[e[i].v])
V.push_back(e[i].id);
}
else if (dfn[e[i].v]<dfn[now]) {
V.push_back(e[i].id);
sum++;
}
}
if ((int)V.size()&1) {
for (int i=1;i<(int)V.size()-1;i++)
ans.push_back(make_pair(V[i],V[i+1]));
ans.push_back(make_pair(V[0],e[las].id));
vis[now]=true;
}
else
for (int i=0;i<(int)V.size()-1;i++)
ans.push_back(make_pair(V[i],V[i+1]));
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
for (int i1=1;i1<=T;i1++) {
cin>>n;int nu=0;
for (int i=1;i<=n;i++) {
cin>>a[i];
b[++nu]=a[i]-i;
b[++nu]=a[i]+i;
}
sort(b+1,b+nu+1);
int cnt=0;
mp.clear();
for (int i=1;i<=nu;i++)
if (mp.find(b[i])==mp.end()) mp[b[i]]=++cnt;
t=1;
for (int i=1;i<=cnt;i++) Link[i]=0;
for (int i=1;i<=n;i++)
Insert(mp[a[i]-i],mp[i+a[i]],i),Insert(mp[a[i]+i],mp[a[i]-i],i);
bool fla=true;ans.clear();
for (int i=1;i<=cnt;i++) dfn[i]=0;
for (int i=1;i<=cnt;i++)
if (!dfn[i]) {
tot=0;sum=0;dfs(i,0);
if (sum&1) {fla=false;break;}
}
if (!fla) cout<<"No"<<'\n';
else {
cout<<"Yes"<<'\n';
for (int i=0;i<(int)ans.size();i++)
cout<<ans[i].first<<' '<<ans[i].second<<'\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5648kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 6 3 5 2 Yes 4 2 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 597ms
memory: 12800kb
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 99977 99979 99821 99823 99988 99986 99980 99981 99976 99974 99970 99968 99949 99947 99929 99930 99922 99921 99909 99908 99904 99902 99891 99890 99880 99878 99846 99847 99835 99833 99827 99828 99810 99811 99805 99804 99802 99800 99789 99788 99786 99787 99782 99783 99777 99778 99775 99774 99755 99...
result:
wrong answer 99892 appears more than once (test case 1)