QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726151#5423. Perfect MatchingASnownAC ✓537ms24796kbC++141.9kb2024-11-08 21:57:452024-11-08 21:57:45

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 21:57:45]
  • 评测
  • 测评结果:AC
  • 用时:537ms
  • 内存:24796kb
  • [2024-11-08 21:57:45]
  • 提交

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);
}

Details

Tip: Click on the bar to expand more detailed information

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)