QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#561839#5423. Perfect Matchinglouhao088#TL 2ms12048kbC++232.7kb2024-09-13 11:27:152024-09-13 11:27:17

Judging History

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

  • [2024-09-13 11:27:17]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:12048kb
  • [2024-09-13 11:27:15]
  • 提交

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());
        }
    }

    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;
}

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

详细

Test #1:

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

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
Time Limit Exceeded

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:


result: