QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588565#5423. Perfect MatchingLongvuWA 240ms79196kbC++142.8kb2024-09-25 13:17:272024-09-25 13:17:27

Judging History

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

  • [2024-09-25 13:17:27]
  • 评测
  • 测评结果:WA
  • 用时:240ms
  • 内存:79196kb
  • [2024-09-25 13:17:27]
  • 提交

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)(2010001);
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();
            dp[i] = -1;
            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();
            // cout << u << " " << n + v << " " << i << '\n';
            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) {
            vector<int> memo;
            while (!adj[u].empty()) {
                pair<int, int> v = adj[u].back();
                adj[u].pop_back();
                if (!vis[v.Se]) {
                    vis[v.Se] = 1;
                    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 (sz(ans) != n / 2) {
            cout << "No" << '\n';
            continue;
        }
        cout << "Yes" << '\n';
        for (auto [u, v] : ans) {
            cout << u << " " << v << '\n';
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 55172kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 240ms
memory: 79196kb

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)