QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267730#5423. Perfect Matchingjrjyy#ML 0ms3536kbC++202.2kb2023-11-27 17:28:512023-11-27 17:28:51

Judging History

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

  • [2023-11-27 17:28:51]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3536kb
  • [2023-11-27 17:28:51]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    int cnt = n;
    std::vector<std::vector<int>> adj(n);
    std::map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        int x = a[i] + i;
        if (!mp.count(x)) {
            mp[x] = cnt++;
            adj.emplace_back();
        }
        adj[i].push_back(mp[x]);
        adj[mp[x]].push_back(i);
    }
    mp.clear();
    for (int i = 0; i < n; ++i) {
        int x = a[i] - i;
        if (!mp.count(x)) {
            mp[x] = cnt++;
            adj.emplace_back();
        }
        adj[i].push_back(mp[x]);
        adj[mp[x]].push_back(i);
    }

    std::vector<bool> vis(cnt);
    std::vector<int> f(cnt, -1);
    std::vector<std::pair<int, int>> ans;
    auto dfs = [&](auto self, int u, int fa) -> void {
        for (auto v : adj[u]) {
            if (v == fa) {
                continue;
            }
            self(self, v, u);
            if (!vis[v]) {
                if (f[u] == -1) {
                    f[u] = v;
                } else {
                    vis[f[u]] = vis[v] = true;
                    ans.emplace_back(f[u], v);
                    f[u] = -1;
                }
            } else if (f[v] != -1) {
                vis[f[v]] = vis[u] = true;
                ans.emplace_back(f[v], u);
                f[v] = -1;
            }
        }
        if (u >= n) {
            vis[u] = true;
        }
    };
    for (int i = n; i < cnt; ++i) {
        if (!vis[i]) {
            dfs(dfs, i, -1);
            if (f[i] != -1) {
                std::cout << "No\n";
                return;
            }
        }
    }
    if (int(ans.size()) * 2 < n) {
        std::cout << "No\n";
        return;
    }

    std::cout << "Yes\n";
    for (auto [u, v] : ans) {
        std::cout << u + 1 << " " << v + 1 << "\n";
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3536kb

input:

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

output:

Yes
1 4
5 2
6 3
Yes
1 3
4 2
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Memory 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: