QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186113#5423. Perfect Matching_LAP_WA 212ms14400kbC++141.9kb2023-09-23 08:02:532023-09-23 08:02:53

Judging History

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

  • [2023-09-23 08:02:53]
  • 评测
  • 测评结果:WA
  • 用时:212ms
  • 内存:14400kb
  • [2023-09-23 08:02:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n, A[N]; vector<pair<int, int>> G[N];
vector<int> lsh; vector<pair<int, int>> ans;

bool vis[N], used[N];
bool dfs(int u, int fa) { vis[u] = true;
    vector<int> E; int flag = 0;
    for(auto &v : G[u]) {
        if(v.second == fa) continue;
        if(v.first != u) {
            if(vis[v.first]) continue;
            dfs(v.first, v.second);
            if(!used[v.second]) E.emplace_back(v.second);
        } else flag = v.second;
    }
    if(flag) E.emplace_back(flag);
    if((int)E.size() % 2 == 1) {
        if(fa == -1) return false;
        else E.emplace_back(fa);
    }
    for(int i = 0; i < E.size(); i += 2)
        ans.push_back({E[i], E[i + 1]}), used[E[i]] = true, used[E[i + 1]] = true;
    return true;
}

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;
        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]) flag = flag && dfs(i, -1);
    if(flag) {
        cout << "Yes\n";
        for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
    } else cout << "No\n";

    // roll back
    for(int i = 1; i <= lsh.size(); i ++) vis[i] = false;
    for(int i = 1; i <= lsh.size(); i ++) G[i].clear();
    for(int i = 1; i <= n; i ++) used[i] = false;
    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: 2ms
memory: 9168kb

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: 212ms
memory: 14400kb

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
7 31
34 79
100 124
130 139
202 205
226 244
289 292
310 316
322 337
364 373
379 382
391 397
418 436
451 460
463 481
511 517
520 526
556 568
586 619
658 661
667 736
754 763
772 790
808 823
826 853
874 904
925 934
964 970
979 988
1003 1009
1027 1030
1048 1078
1090 1105
1162 1171
1216 1219
1228 1273...

result:

wrong answer abs(130-139) != abs(a[130]-a[139]) (test case 1)