QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230634#5423. Perfect MatchingMyCallAC ✓380ms36296kbC++143.1kb2023-10-28 19:58:292023-10-28 19:58:29

Judging History

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

  • [2023-10-28 19:58:29]
  • 评测
  • 测评结果:AC
  • 用时:380ms
  • 内存:36296kb
  • [2023-10-28 19:58:29]
  • 提交

answer

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
#define Wild_Donkey 0
#define foreplay for
#define wild while
using namespace std;
inline unsigned RD() {
  unsigned intmp(0);
  char rdch(getchar());
  while (rdch < '0' || rdch > '9') rdch = getchar();
  while (rdch >= '0' && rdch <= '9')
    intmp = (intmp << 3) + (intmp << 1) + rdch - '0', rdch = getchar();
  return intmp;
}
inline int RDsg() {
  int rdtp(0), rdsg(1);
  char rdch(getchar());
  while ((rdch < '0' || rdch > '9') && (rdch != '-')) rdch = getchar();
  if (rdch == '-') rdsg = -1, rdch = getchar();
  while (rdch >= '0' && rdch <= '9')
    rdtp = (rdtp << 3) + (rdtp << 1) + rdch - '0', rdch = getchar();
  return rdtp * rdsg;
}
unsigned a[100005], b[100005], c[100005];
unsigned n, na, nb, A, B, t;
unsigned Cnt(0), Ans[50005][2];
char EdV[100005], Flg(0);
struct Node {
  vector<pair<Node*, unsigned> > Edge;
  char Vis;
  inline char DFS(unsigned Pre) {
    // printf("DFS %u %u\n", Pre, Cnt);
    Vis = 1;
    unsigned Lst(0), Cur(0);
    for (auto i : Edge) {
      Cur = i.second;
      if (!EdV[Cur]) {
        EdV[Cur] = 1;
        if ((!i.first->Vis) && (!i.first->DFS(Cur))) Cur = 0;
        if (Cur) {
          if (Lst)
            Ans[++Cnt][0] = Lst, Ans[Cnt][1] = Cur, Lst = 0;
          else
            Lst = Cur;
        }
      }
    }
    // printf("Lst %u\n", Lst);
    if (!Lst) return 1;
    if (Pre) Ans[++Cnt][0] = Pre, Ans[Cnt][1] = Lst;
    return 0;
  }
} N[200005];
inline void Clr() {
  memset(EdV, 0, n + 2);
  for (unsigned i(na + nb); i; --i) N[i].Edge.clear(), N[i].Vis = 0;
  n = RD(), Flg = Cnt = na = nb = 0;
}
signed main() {
  //  freopen(".in", "r", stdin);
  //  freopen(".out", "w", stdout);
  t = RD();
  for (unsigned T(1); T <= t; ++T) {
    Clr();
    for (unsigned i(1); i <= n; ++i) {
      A = RDsg() + 1000100000;
      a[i] = A - i;
      b[i] = A + i;
    }
    for (unsigned i(1); i <= n; ++i) c[i] = a[i];
    sort(c + 1, c + n + 1);
    na = unique(c + 1, c + n + 1) - c - 1;
    for (unsigned i(1); i <= n; ++i)
      a[i] = lower_bound(c + 1, c + na + 1, a[i]) - c;
    for (unsigned i(1); i <= n; ++i) c[i] = b[i];
    sort(c + 1, c + n + 1);
    nb = unique(c + 1, c + n + 1) - c - 1;
    for (unsigned i(1); i <= n; ++i)
      b[i] = lower_bound(c + 1, c + nb + 1, b[i]) - c;
    for (unsigned i(1); i <= n; ++i) {
      A = a[i], B = b[i];
      N[A].Edge.push_back({N + na + B, i});
      N[na + B].Edge.push_back({N + A, i});
    }
    for (unsigned i(1); i <= na; ++i)
      if (!N[i].Vis) Flg |= (!N[i].DFS(0));
    if ((Cnt << 1) != n) {
      printf("No\n");
    } else {
      printf("Yes\n");
      for (unsigned i(1); i <= Cnt; ++i)
        printf("%u %u\n", Ans[i][0], Ans[i][1]);
    }
  }
  //  system("pause");
  return Wild_Donkey;
}
/*
2
6
1 2 3 4 -3 2
4
1 2 3 0
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 208ms
memory: 35040kb

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
14 15
16 20
77 78
3 79
137 138
200 201
139 202
244 242
289 287
308 309
314 315
310 316
320 321
337 335
382 380
395 396
322 397
449 450
458 459
451 460
461 462
479 480
463 481
517 515
520 518
526 524
556 554
566 567
619 617
659 660
568 661
736 734
763 761
790 788
853 851
902 903
932 933
904 934
9...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 2ms
memory: 10076kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 145ms
memory: 36296kb

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
29329 29330
29331 29332
29333 29334
29335 29336
29337 29338
29339 29340
29341 29342
29343 29344
29345 29346
29347 29348
29349 29350
29352 29351
71753 71754
71755 71756
71757 71758
71759 71760
71761 71762
71763 71764
71765 71766
71767 71768
71769 71770
71771 71772
71773 71774
71775 71776
71777 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 380ms
memory: 24880kb

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
8564 26518
1121 63463
57 58
49 54
36817 36811
84 129
8931 95315
506 7625
55 73
13 14
28 89504
153 222
711 797
47 48
99 152
70110 81303
13611 16772
126 132
778 34736
62 7528
128 159
109 193
859 1003
92 127
435 443
80963 80784
821 11544
80993 88310
940 74032
33052 80608
188 559
155 164
1661 3199
3...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 118ms
memory: 11724kb

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
14 15
20 24
3 5
26 28
29 38
41 43
45 49
57 59
68 70
74 75
71 83
112 113
87 118
119 122
124 126
130 131
129 134
139 141
142 144
143 146
151 152
165 167
170 171
175 177
183 185
184 186
200 202
178 203
205 207
212 213
208 219
220 221
243 245
226 257
266 267
271 272
268 270
273 274...

result:

ok 1000 Cases (1000 test cases)