QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561860#5423. Perfect Matchinglouhao088#WA 456ms24876kbC++232.8kb2024-09-13 11:48:042024-09-13 11:48:04

Judging History

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

  • [2024-09-13 11:48:04]
  • 评测
  • 测评结果:WA
  • 用时:456ms
  • 内存:24876kb
  • [2024-09-13 11:48:04]
  • 提交

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 (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() {
    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: 0ms
memory: 9888kb

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: 456ms
memory: 24876kb

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
99966 99965
99962 99963
34 139
202 310
316 322
397 451
460 463
481 661
763 904
934 988
1219 1294
1561 1618
1684 1738
1915 2029
2290 2509
2530 2551
2695 2800
2818 2821
2914 2923
3061 3142
3154 3343
3496 3589
3784 3952
3988 4069
4504 4891
4948 5056
5197 5467
5506 5551
5752 5767
5773 5821
5905 5938...

result:

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