QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186126 | #5423. Perfect Matching | _LAP_ | WA | 266ms | 36376kb | C++14 | 2.3kb | 2023-09-23 08:50:24 | 2023-09-23 08:50:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, A[N]; vector<int> E[N]; vector<pair<int, int>> G[N];
vector<int> lsh; vector<pair<int, int>> ans;
bool vis[N], used[N];
int dep[N], fa[N]; vector<int> vec;
void dfs(int u, int Fa) {
vis[u] = true, fa[u] = Fa, dep[u] = dep[Fa] + 1; vec.emplace_back(u);
for(auto &v : G[u])
if(!vis[v.first]) dfs(v.first, u);
}
inline void solve() {
cin >> n;
for(int i = 1; i <= n; i ++) cin >> A[i];
for(int i = 1; i <= n; i ++) lsh.emplace_back(i - A[i]), lsh.emplace_back(i + A[i]);
sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
for(int i = 1; i <= n; i ++) {
int a = lower_bound(lsh.begin(), lsh.end(), i - A[i]) - lsh.begin() + 1;
int b = lower_bound(lsh.begin(), lsh.end(), i + A[i]) - lsh.begin() + 1;
if(a == b) E[a].emplace_back(i);
else G[a].push_back({b, i}), G[b].push_back({a, i});
}
bool flag = true;
for(int i = 1; i <= lsh.size(); i ++) if(!vis[i]) {
vec.clear(); dfs(i, 0); sort(vec.begin(), vec.end(), [](int a, int b) {return dep[a] > dep[b]; });
for(auto &u : vec) {
for(auto &v : G[u]) {
if(v.first == fa[u]) continue;
if(!used[v.second]) E[u].emplace_back(v.second);
}
if((int)E[u].size() % 2 == 1) {
if(fa[u] == 0) {flag = false; break; }
else E[u].emplace_back((lsh[u - 1] + lsh[fa[u] - 1]) / 2), assert((lsh[u - 1] + lsh[fa[u] - 1]) % 2 == 0);
}
for(int j = 0; j < E[u].size(); j += 2)
assert((!used[E[u][j]]) && (!used[E[u][j + 1]])), used[E[u][j]] = used[E[u][j + 1]] = true, ans.push_back({E[u][j], E[u][j + 1]});
}
if(!flag) break;
}
if(flag) {
cout << "Yes\n";
for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
} else cout << "No\n";
for(int i = 1; i <= lsh.size(); i ++) vis[i] = false;
for(int i = 1; i <= n; i ++) used[i] = false;
for(int i = 1; i <= lsh.size(); i ++) E[i].clear(), G[i].clear();
lsh.clear(), ans.clear();
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 28040kb
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 4 1 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 266ms
memory: 36376kb
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 49521 49520 49608 49607 49400 49402 49485 49486 49697 49699 49368 49367 49562 49564 49323 49322 49657 49656 49416 49415 49465 49464 49725 49724 49363 49362 49510 49509 49314 49313 49535 49537 49389 49388 49574 49576 49275 49274 49633 49632 49408 49407 49680 49679 49331 49333 49711 49710 49441 49...
result:
wrong answer abs(140-147) != abs(a[140]-a[147]) (test case 1)