QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186126#5423. Perfect Matching_LAP_WA 266ms36376kbC++142.3kb2023-09-23 08:50:242023-09-23 08:50:24

Judging History

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

  • [2023-09-23 08:50:24]
  • 评测
  • 测评结果:WA
  • 用时:266ms
  • 内存:36376kb
  • [2023-09-23 08:50:24]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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)