QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334604#5423. Perfect MatchingyllcmAC ✓1048ms19480kbC++141.7kb2024-02-22 08:48:352024-02-22 08:48:36

Judging History

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

  • [2024-02-22 08:48:36]
  • 评测
  • 测评结果:AC
  • 用时:1048ms
  • 内存:19480kb
  • [2024-02-22 08:48:35]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 2e5 + 10;
int n;
int a[N], vis[N], vm[N];
vector<pii> G[N];
vector<pii> mat;
void dfs(int u, int fid) {
  vector<int> V;
  for(auto t : G[u]) {
    int id = t.FR, v = t.SE;
    if(vis[v]) {if(!vm[id] && id != fid)V.pb(id); continue;}
    vis[v] = true; dfs(v, id);
    if(!vm[id])V.pb(id);
  }
  if((V.size() & 1) && fid)V.pb(fid);
  for(int i = 0; i + 1 < V.size(); i += 2)
    vm[V[i]] = vm[V[i + 1]] = true, mat.pb({V[i], V[i + 1]});
  return ;
}
void solve() {
  n = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  map<int, int> id[2]; int tot = 0;
  for(int i = 1; i <= n; i++) {
    if(!id[0].count(i + a[i]))id[0][i + a[i]] = ++tot;
    if(!id[1].count(i - a[i]))id[1][i - a[i]] = ++tot;
    G[id[0][i + a[i]]].pb({i, id[1][i - a[i]]});
    G[id[1][i - a[i]]].pb({i, id[0][i + a[i]]});
  }
  vector<pii>().swap(mat);
  for(int i = 1; i <= tot; i++)if(!vis[i])vis[i] = true, dfs(i, 0);
  for(int i = 1; i <= tot; i++) {
    vector<pii>().swap(G[i]);
    vis[i] = false;
  }
  for(int i = 1; i <= n; i++)vm[i] = false;
  if(mat.size() != n / 2)return puts("No"), void();
  puts("Yes");
  for(auto t : mat)printf("%d %d\n", t.FR, t.SE);
  return ;
}
int main() {
  int test = read();
  while(test--)solve();
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8468kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
1 4
5 2
6 3
Yes
1 3
4 2
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 307ms
memory: 16684kb

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
77 78
137 138
200 201
242 244
287 289
308 309
314 315
320 321
335 337
380 382
395 396
449 450
458 459
461 462
479 480
515 517
518 520
524 526
554 556
566 567
617 619
659 660
734 736
761 763
788 790
851 853
902 903
932 933
977 978
986 987
1088 1089
1103 1104
1160 1162
1217 1218
1271 1273
1283 128...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 8660kb

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
2 3
4 5
6 7
8 1
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
36 37
38 35
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
58 39
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 356ms
memory: 19480kb

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
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
20 21
22 23
24 25
26 27
28 29
30 31
32 33
34 35
36 37
38 39
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
58 59
60 61
62 63
64 65
66 67
68 69
70 71
72 73
74 75
76 77
78 79
80 81
82 83
84 85
86 87
88 89
90 91
92 93
94 95
96 97
98 99
100 101
10...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 1048ms
memory: 18376kb

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
89504 28
8564 26518
63463 1121
36811 36817
8931 95315
96991 61541
81132 92548
41302 83637
34736 778
12537 4360
99552 2005
97953 92893
58176 30631
70597 19622
37677 26691
27149 66364
67617 10211
17075 44140
57643 11472
23176 35741
95323 12598
9050 10585
68565 28519
21782 10746
1793 47710
63141 55...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 217ms
memory: 8516kb

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
23 22
34 33
48 47
73 72
108 107
128 127
148 147
156 155
180 179
193 192
211 210
261 260
263 262
310 309
319 318
343 342
405 404
407 406
418 417
444 443
456 455
503 502
584 583
600 599
664 663
700 699
705 704
719 718
721 720
728 727
740 739
771 770
858 857
913 912
952 951
963 96...

result:

ok 1000 Cases (1000 test cases)