QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561887#5423. Perfect Matchinglouhao088#WA 404ms26300kbC++232.8kb2024-09-13 12:03:122024-09-13 12:03:12

Judging History

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

  • [2024-09-13 12:03:12]
  • 评测
  • 测评结果:WA
  • 用时:404ms
  • 内存:26300kb
  • [2024-09-13 12:03:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

int re, zf; char C;
int read() {
    re = 0; zf = 1;
    C = getchar();
    while (C < '0' || C > '9') {
        if (C == '-') zf = -zf;
        C = getchar();
    }
    while (C >= '0' && C <= '9') {
        re = re * 10 + C - '0';
        C = getchar();
    }
    return re * zf;
}

const int N = 3e5 + 100;
int n, a[N], b[N], c[N];
int bb[N], cc[N], du[N];

struct node {
    int x, to, nxt;
}e[N];
int le[N], KK;
void add(int x, int y, int i) {
    e[++KK] = (node){i, y, le[x]}; le[x] = KK;
    e[++KK] = (node){i, x, le[y]}; le[y] = KK;
}
vector <int> ans[N];
queue <int> q;
set <int> line;
bool in[N];

void del(int i) {
    in[i] = 1; line.erase(i);
    int l = b[i], r = c[i];
    if (du[r] == 1) swap(l, r);
    if (du[l] != 1 && (rand() & 1)) swap(l, r);
    if (ans[l].size() & 1) ans[l].push_back(i);
        else ans[r].push_back(i);
    du[l]--; du[r]--;
    if (du[l] == 1) q.push(l);
    if (du[r] == 1) q.push(r);
}

void slove() {
    srand(time(0));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i] - i; c[i] = a[i] + i;
        bb[i] = b[i]; cc[i] = c[i];
    }
    sort(bb + 1, bb + n + 1); sort(cc + 1, cc + n + 1);
    int bn = unique(bb + 1, bb + n + 1) - bb - 1, cn = unique(cc + 1, cc + n + 1) - cc - 1;
    for (int i = 1; i <= n; i++) {
        b[i] = lower_bound(bb + 1, bb + bn + 1, b[i]) - bb;
    }
    for (int i = 1; i <= n; i++) {
        c[i] = lower_bound(cc + 1, cc + cn + 1, c[i]) - cc + bn;
    }
    for (int i = 1; i <= n; i++) du[b[i]]++, du[c[i]]++, add(b[i], c[i], i), line.insert(i);
    for (int i = 1; i <= n; i++) in[i] = 0;

    for (int i = 1; i <= bn + cn; i++)
        if (du[i] == 1) q.push(i);
    int num = 0;
    while (num < n) {
        while (!q.empty()) {
            int now = q.front(); q.pop();
            for (int i = le[now]; i; i = e[i].nxt)
                if (!in[e[i].x]) {
                    del(e[i].x); num++;
                }
        }
        if (num < n) {
            del(*line.begin()); num++;
        }
    }

    bool yes = 1;
    for (int i = 1; i <= bn + cn; i++) {
        if (ans[i].size() & 1) {
            yes = 0; break;
        }
    }
    if (yes) {
        printf("Yes\n");
        for (int i = 1; i <= bn + cn; i++) {
            for (int j = 0; j + 1 < ans[i].size(); j += 2)
                printf("%d %d\n", ans[i][j], ans[i][j + 1]);
        }
    }
    else {
        printf("No\n");
    }

    line.clear();
    while (!q.empty()) q.pop();
    for (int i = 1; i <= bn + cn; i++) du[i] = 0, ans[i].clear();
    for (int i = 1; i <= n; i++) in[i] = 0;
    for (int i = 1; i <= bn + cn; i++) le[i] = 0; KK = 0;
}

int main()
{
    int t = read();
    while (t--) slove();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 404ms
memory: 26300kb

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:

No
No
No
Yes
99993 99992
99982 99980
99977 99979
99966 99967
99887 99888
99867 99868
99840 99841
99807 99808
99792 99793
99716 99717
99689 99690
99674 99675
99653 99654
99642 99643
99582 99583
99572 99573
99563 99565
99548 99550
99534 99535
99518 99519
99515 99516
99506 99507
99458 99460
99429 99430...

result:

wrong answer std outputs a valid answer while participant doesn't (test case 1)