QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106457#5423. Perfect MatchingcokleWA 5ms8456kbC++112.6kb2023-05-17 20:31:492023-05-17 20:31:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 20:31:54]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:8456kb
  • [2023-05-17 20:31:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, M = N << 1;

int t, n, tot;
int a[N], cnt[N], pre[N], vis[N];
int head[N], ver[M], nxt[M], idx;

inline void add(int x, int y) {
    ver[++idx] = y, nxt[idx] = head[x], head[x] = idx;
}

inline bool dfs(int u) {
    for (int i = head[u], v; i; i = nxt[i]) {
        v = ver[i];
        if (vis[v]) continue;
        vis[v] = 1;
        if (!pre[v] || dfs(pre[v])) {
            pre[v] = u;
            return true;
        }
    }
    return false;
}

inline bool check(int x) {
    memset(head, 0, sizeof head);
    memset(pre, 0, sizeof pre);
    memset(cnt, 0, sizeof cnt);
    idx = 0, tot = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] < x) continue;
        ++cnt[a[i] - x + 1], ++tot;
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i] < x || a[i] >= x + n) continue;
        add(i, cnt[a[i] - x] + 1);
    }
    for (int i = 1; i <= tot; ++i) {
        memset(vis, 0, sizeof vis);
        if (!dfs(i)) return false;
    }
    return true;
}

signed main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        int l = 0, r = n >> 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(a[mid + 1] - a[mid])) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (check(a[l + 1] - a[l])) {
            cout << "Yes" << endl;
            for (int i = 1; i <= n; ++i) {
                if (a[i] < a[l + 1] && a[i] >= a[l + 1] - n) {
                    for (int j = head[cnt[a[i] - a[l] + 1] + 1]; j; j = nxt[j]) {
                        if (ver[j] <= n && ver[j] > 0 && abs(a[ver[j]] - a[i]) == a[l + 1] - a[l]) {
                            cout << i << " " << ver[j] << endl;
                            pre[ver[j]] = 1;
                            break;
                        }
                    }
                }
            }
            for (int i = 1; i <= n; ++i) {
                if (pre[i]) continue;
                for (int j = head[cnt[a[i] - a[l] + 1] + 1]; j; j = nxt[j]) {
                    if (ver[j] <= n && ver[j] > 0 && abs(a[ver[j]] - a[i]) == a[l + 1] - a[l]) {
                        cout << i << " " << ver[j] << endl;
                        break;
                    }
                }
            }
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 8456kb

input:

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

output:

No
No
No

result:

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