QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561902#5423. Perfect Matchinglouhao088#WA 391ms25192kbC++232.9kb2024-09-13 12:37:352024-09-13 12:37:37

Judging History

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

  • [2024-09-13 12:37:37]
  • 评测
  • 测评结果:WA
  • 用时:391ms
  • 内存:25192kb
  • [2024-09-13 12:37:35]
  • 提交

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) {
                if (abs(ans[i][j] - ans[i][j + 1]) != abs(a[ans[i][j]] - a[ans[i][j + 1]])) while (1);
                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: 12160kb

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: 391ms
memory: 25192kb

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
99986 99988
99974 99976
99968 99970
99966 99965
99962 99963
99947 99949
99933 99934
99921 99922
99919 99917
99914 99916
99896 99897
99878 99880
99836 99837
99804 99805
99800 99802
99773 99775
99740 99741
99690 99691
99657 99658
99641 99642
99629 99630
99608 99610
99578 99579
99572 99573
99557 99...

result:

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