QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#732518 | #5423. Perfect Matching | PorNPtree | WA | 257ms | 13272kb | C++23 | 1.5kb | 2024-11-10 14:58:01 | 2024-11-10 14:58:01 |
Judging History
answer
#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+5;
int T,n,m,a[N],b[N],sz[N],fa[N];
vector<P>g[N],ans;bool v[N],ban[N];
inline int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
inline void hb(int x,int y)
{
x=getf(x),y=getf(y);sz[x]++;
if(x^y) fa[y]=x,sz[x]+=sz[y];
}
inline void add(int u,int v,int w)
{
hb(u,v);//cout<<u<<" "<<v<<" "<<w<<"\n";
g[u].push_back({v,w}),g[v].push_back({u,w});
}
inline bool chk()
{
for(int i=1;i<=m;i++) if(sz[getf(i)]&1) return 0;
return 1;
}
void dfs(int x,int las)
{
v[x]=1;
for(auto [y,w]:g[x]) if(!v[y]) dfs(y,w);
vector<int>nw;
for(auto [y,w]:g[x]) if(!ban[w]&&w!=las) nw.push_back(w);
if(nw.size()&1) nw.push_back(las);
for(int i:nw) ban[i]=1;
for(int i=0;i<nw.size()/2;i++) ans.push_back({nw[i<<1],nw[i<<1|1]});
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
while(T--)
{
cin>>n;m=0;ans.clear();
for(int i=1;i<=n;i++) cin>>a[i],b[++m]=i-a[i],b[++m]=i+a[i],ban[i]=0;
sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;
for(int i=1;i<=m;i++) fa[i]=i,sz[i]=0,g[i].clear(),v[i]=0;
#define ls(x) lower_bound(b+1,b+1+m,x)-b
for(int i=1;i<=n;i++) add(ls(i-a[i]),ls(i+a[i]),i);
if(!chk()){cout<<"No\n";continue;}
for(int i=1;i<=m;i++) if(!v[i]) dfs(i,0);
cout<<"Yes\n";
for(auto [u,v]:ans) cout<<u<<" "<<v<<"\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5844kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 3 6 2 5 4 1 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 257ms
memory: 13272kb
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 11 12 21 22 5 7 29 30 32 33 77 78 98 99 122 123 128 129 137 138 200 201 203 205 224 225 242 244 287 289 290 291 308 309 314 315 320 321 335 337 362 364 371 372 377 378 380 382 389 391 395 396 416 417 434 435 449 450 458 459 461 462 479 480 509 511 515 517 518 520 524 526 554 556 566 567 584 586 ...
result:
wrong answer abs(3-31) != abs(a[3]-a[31]) (test case 1)