QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73623#5423. Perfect Matchinghos_lyricWA 285ms13668kbC++143.1kb2023-01-26 19:18:482023-01-26 19:18:49

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:18:49]
  • 评测
  • 测评结果:WA
  • 用时:285ms
  • 内存:13668kb
  • [2023-01-26 19:18:48]
  • 提交

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<pair<int, int>> ans;

int dfs(int u, int p) {
  vis[u] = 1;
  int ret = -1;
  for (const int i : G[u]) {
    const int v = A[i] ^ B[i] ^ u;
    if (!vis[v]) {
      const int res = dfs(v, u);
      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);
    ans.clear();
    for (int u = 0; u < N; ++u) if (!vis[u]) {
      const int res = dfs(u, -1);
      if (~res) {
        goto failed;
      }
    }
    
    puts("Yes");
    for (const auto &p : ans) {
      printf("%d %d\n", p.first + 1, p.second + 1);
    }
    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: 1ms
memory: 3588kb

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: -100
Wrong Answer
time: 285ms
memory: 13668kb

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
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 ...

result:

wrong output format Expected integer, but "Yes" found (test case 1)