QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73624#5423. Perfect Matchinghos_lyricAC ✓571ms17528kbC++143.2kb2023-01-26 19:24:052023-01-26 19:24:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-26 19:24:07]
  • 评测
  • 测评结果:AC
  • 用时:571ms
  • 内存:17528kb
  • [2023-01-26 19:24:05]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int M;
vector<Int> Y;

int N;
vector<int> A, B;

vector<vector<int>> G;
vector<int> vis;
vector<int> used;
vector<pair<int, int>> ans;

int dfs(int u, int pi) {
  vis[u] = 1;
  int ret = -1;
  for (const int i : G[u]) if (!used[i]) {
    used[i] = 1;
    const int v = A[i] ^ B[i] ^ u;
    int res = -1;
    if (!vis[v]) {
      res = dfs(v, i);
    }
    if (~res) {
      ans.emplace_back(i, res);
    } else {
      if (~ret) {
        ans.emplace_back(ret, i);
        ret = -1;
      } else {
        ret = i;
      }
    }
  }
  return ret;
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d", &M);
    Y.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%lld", &Y[i]);
    }
    
    vector<Int> ps(M), qs(M);
    for (int i = 0; i < M; ++i) {
      ps[i] = Y[i] + i;
      qs[i] = Y[i] - i;
    }
    sort(ps.begin(), ps.end());
    sort(qs.begin(), qs.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    qs.erase(unique(qs.begin(), qs.end()), qs.end());
    const int psLen = ps.size();
    const int qsLen = qs.size();
    N = psLen + qsLen;
    A.resize(M);
    B.resize(M);
    for (int i = 0; i < M; ++i) {
      A[i] = lower_bound(ps.begin(), ps.end(), Y[i] + i) - ps.begin();
      B[i] = lower_bound(qs.begin(), qs.end(), Y[i] - i) - qs.begin();
      B[i] += psLen;
    }
// cerr<<"A = "<<A<<", B = "<<B<<endl;
    
    G.assign(N, {});
    for (int i = 0; i < M; ++i) {
      G[A[i]].push_back(i);
      G[B[i]].push_back(i);
    }
    vis.assign(N, 0);
    used.assign(M, 0);
    ans.clear();
    for (int u = 0; u < N; ++u) if (!vis[u]) {
      const int res = dfs(u, 0);
      if (~res) {
        goto failed;
      }
    }
    
    puts("Yes");
    for (const auto &p : ans) {
      printf("%d %d\n", p.first + 1, p.second + 1);
    }
    assert(2 * (int)ans.size() == M);
    continue;
   failed:{}
    puts("No");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3612kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 318ms
memory: 14188kb

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: 3ms
memory: 3636kb

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
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
39 58
29 30
31 32
33 34
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
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
59 60
61 62
63 64
65 66
67 68
36 37
35 38
2 3
4 5
6 7
1 8
69 70
71 72
73 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 283ms
memory: 17528kb

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
29351 29352
71754 71755
71756 71757
71758 71759
71760 71761
71762 71763
71764 71765
71766 71767
71768 71769
71770 71771
71772 71773
71774 71775
71776 71777
71778 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 571ms
memory: 15436kb

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
47 48
13 14
28 89504
49 54
57 58
8564 26518
1121 63463
153 222
36817 36811
84 129
8931 95315
506 7625
536 1600
61541 96991
126 132
14495 23105
33602 36346
99 152
107 243
81132 92548
8961 29263
41302 83637
11086 16914
62 7528
859 1003
92 127
513 768
66 118
288 2392
778 34736
4360 12537
542 664
20...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 209ms
memory: 3780kb

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
4 11
6 9
16 17
18 21
22 23
25 27
31 32
33 34
35 42
47 48
51 62
72 73
64 79
82 86
90 96
101 103
107 108
109 111
127 128
121 145
147 148
155 156
157 159
164 166
169 174
179 180
176 191
192 193
195 201
210 211
204 223
229 230
237 244
246 252
260 261
262 263
269 276
282 292
293 294...

result:

ok 1000 Cases (1000 test cases)