QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106457 | #5423. Perfect Matching | cokle | WA | 5ms | 8456kb | C++11 | 2.6kb | 2023-05-17 20:31:49 | 2023-05-17 20:31:54 |
Judging History
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)