QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#588518 | #5423. Perfect Matching | Longvu | WA | 201ms | 23396kb | C++14 | 2.7kb | 2024-09-25 12:40:29 | 2024-09-25 12:40:30 |
Judging History
answer
/**
* author: longvu
* created: 09/25/24 11:09:40
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(201001);
const int mod = 1e9 + 7;
template<class X, class Y>
bool maximize(X& x, const Y y) {
if (y > x) {x = y; return true;}
return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
if (y < x) {x = y; return true;}
return false;
}
#define Fi first
#define Se second
int a[nax], vis[nax], dp[nax];
vector<pair<int, int>> adj[nax];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
for (int i = 1; i <= 2 * n; ++i) {
adj[i].clear();
vis[i] = 0;
}
vector<int> valuex = { -INF}, valuey = { -INF};
for (int i = 1; i <= n; ++i) {
cin >> a[i];
valuex.push_back(i - a[i]);
valuey.push_back(i + a[i]);
}
sort(all(valuex));
valuex.resize(unique(all(valuex)) - valuex.begin());
sort(all(valuey));
valuey.resize(unique(all(valuey)) - valuey.begin());
for (int i = 1; i <= n; ++i) {
int u = lower_bound(all(valuex), i - a[i]) - valuex.begin()
, v = lower_bound(all(valuey), i + a[i]) - valuey.begin();
adj[u].push_back({n + v, i});
adj[n + v].push_back({u, i});
}
vector<pair<int, int>> ans;
function<void(int)> dfs = [&](int u) {
vis[u] = 1;
dp[u] = -1;
vector<int> memo;
for (auto v : adj[u]) {
if (!vis[v.Fi]) {
dfs(v.Fi);
if (dp[v.Fi] == -1) {
memo.push_back(v.Se);
} else {
ans.push_back({v.Se, dp[v.Fi]});
}
}
}
for (int i = 0; i + 1 < sz(memo); i += 2) {
ans.push_back({memo[i], memo[i + 1]});
}
if (sz(memo) % 2) {
dp[u] = memo.back();
}
};
for (int i = 1; i <= 2 * n; ++i) {
if (!vis[i]) {
dfs(i);
// if (dp[i] != -1) {
// break;
// }
}
}
if (sz(ans) != n / 2) {
cout << "No" << '\n';
continue;
}
cout << "Yes" << '\n';
for (auto [u, v] : ans) {
cout << u << " " << v << '\n';
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11464kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 3 6 2 5 1 4 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 201ms
memory: 23396kb
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:
No No No No No No No No No No
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)