QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588518#5423. Perfect MatchingLongvuWA 201ms23396kbC++142.7kb2024-09-25 12:40:292024-09-25 12:40:30

Judging History

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

  • [2024-09-25 12:40:30]
  • 评测
  • 测评结果:WA
  • 用时:201ms
  • 内存:23396kb
  • [2024-09-25 12:40:29]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)