QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726151 | #5423. Perfect Matching | ASnown | AC ✓ | 537ms | 24796kb | C++14 | 1.9kb | 2024-11-08 21:57:45 | 2024-11-08 21:57:45 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popcount(x) (__builtin_popcount((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int N = 2e5+25;
int n;
int a[N];
vector<int> VL,VR;
vector<pair<int,int>> e[N];
int dep[N];
vector<pair<int,int>> G;
int dfs(int u,int fa) {
dep[u]=dep[fa]+1;
vector<int> es;
for(auto [v,id]:e[u]) if(!dep[v]) {
auto p=dfs(v,u);
if(p) G.emplace_back(id,p);
else es.emplace_back(id);
} else if(dep[v]>dep[u])
es.emplace_back(id);
for(int i=0;i+1<es.size();i+=2)
G.emplace_back(es[i],es[i+1]);
return (es.size()&1)?es.back():0;
}
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int T; cin>>T; while(T--)
Solve();
}
void Solve() {
VL.clear(),VR.clear(),G.clear();
for(int i=1;i<=n+n;i++) e[i].clear(),dep[i]=0;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
VL.emplace_back(i-a[i]);
VR.emplace_back(i+a[i]);
}
sort(ALL(VL)),VL.erase(unique(ALL(VL)),VL.end());
sort(ALL(VR)),VR.erase(unique(ALL(VR)),VR.end());
for(int i=1;i<=n;i++) {
int l=upper_bound(ALL(VL),i-a[i])-VL.begin();
int r=upper_bound(ALL(VR),i+a[i])-VR.begin()+n;
e[l].emplace_back(r,i);
e[r].emplace_back(l,i);
}
for(int i=1;i<=n+n;i++) if(!dep[i]&&dfs(i,0))
return void(puts("No"));
puts("Yes");
assert(G.size()==n/2);
for(auto [u,v]:G) printf("%d %d\n",u,v);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8844kb
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 1 4 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 239ms
memory: 15144kb
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 79 139 202 244 289 310 316 322 337 382 397 451 460 463 481 517 520 526 556 568 619 661 736 763 790 853 904 934 979 988 1090 1105 1162 1219 1273 1285 1294 1405 1411 1456 1459 1531 1555 1561 1588 1615 1618 1630 1651 1669 1684 1723 1738 1915 1972 2026 2029 2092 2155 2197 2290 2305 2350 2353 2419 24...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 8936kb
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 70 71 72 73 69 74 1 2 3 4 5 6 7 8 35 36 37 38 60 61 62 63 64 65 66 67 59 68 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 9 28 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 75 100 30 31 32 33 29 34 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 232ms
memory: 24796kb
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 49559 49560 29353 29354 29355 29356 29357 29358 29359 29360 29361 29362 29363 29364 29365 29366 29367 29368 29369 29370 29371 29372 29373 29374 29375 29376 29377 29378 29379 29380 29381 29382 29383 29384 29385 29386 29387 29388 29389 29390 29391 29392 29393 29394 29395 29396 29397 29398 33954 33...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 537ms
memory: 18612kb
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 28 89504 8564 26518 1121 63463 129 36817 8931 95315 61541 96991 70110 81303 13611 16772 778 34736 80993 88310 11544 74032 33052 80608 37367 78597 65442 84943 20961 50244 52881 91157 6609 10333 3408 19162 59542 87006 416 97729 23980 79681 27149 66364 10211 67617 17075 44140 11472 57643 18857 3304...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 138ms
memory: 8928kb
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 Yes 2 10 15 19 44 52 59 60 63 67 78 80 84 95 97 99 100 115 117 131 140 144 162 167 168 185 186 189 196 197 199 202 206 207 209 215 216 217 218 233 234 238 239 245 247 248 253 258 264 265 272 280 281 286 290 305 308 314 316 321 322 327 330 334 353 360 362 369 372 379 380 385 388 408...
result:
ok 1000 Cases (1000 test cases)