QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#263685 | #5423. Perfect Matching | KhNURE_KIVI | AC ✓ | 466ms | 24888kb | C++23 | 3.6kb | 2023-11-25 02:58:44 | 2023-11-25 02:58:44 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef __APPLE__
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif
const int max_n = 1e5 + 42, inf = 1000111222;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int, int> > g[max_n * 2];
int h[max_n * 2];
bool used[max_n];
vector<pair<int, int> > ans;
void dfs(int v, int par, int par_edg) {
for(auto& to : g[v])
if(h[to.fi] == -1) {
h[to.fi] = h[v] + 1;
dfs(to.fi, to.fi, to.se);
}
vector<int> edges;
for(auto& to : g[v])
if(!used[to.se] && h[to.fi] > h[v])
edges.pb(to.se);
if(len(edges) % 2 && par_edg != -1) edges.pb(par_edg);
for(int i = 1; i < len(edges); i += 2) {
used[edges[i]] = used[edges[i - 1]] = true;
ans.pb({edges[i], edges[i - 1]});
}
}
void solve() {
ans.clear();
int n;
cin >> n;
vector<int> a(n);
vector<int> bs, cs;
for(int i = 0; i < n; i++) {
cin >> a[i];
bs.pb(a[i] - i);
cs.pb(a[i] + i);
}
sort(all(bs));
sort(all(cs));
bs.resize(unique(all(bs)) - bs.begin());
cs.resize(unique(all(cs)) - cs.begin());
for(int i = 0; i < n; i++) {
int b_ind = lower_bound(all(bs), a[i] - i) - bs.begin();
int c_ind = lower_bound(all(cs), a[i] + i) - cs.begin();
g[b_ind].pb({len(bs) + c_ind, i});
g[len(bs) + c_ind].pb({b_ind, i});
}
for(int v = 0; v < len(bs) + len(cs); v++) {
if(h[v] != -1) continue;
dfs(v, -1, -1);
}
if(len(ans) != n / 2) cout << "No\n";
else {
cout << "Yes\n";
for(auto& x : ans) cout << x.fi + 1 << ' ' << x.se + 1 << '\n';
}
for(int i = 0; i < n; i++) used[i] = false;
for(int i = 0; i < len(bs) + len(cs); i++) { g[i].clear(); h[i] = -1; }
}
signed main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i = 0; i < max_n * 2; i++) h[i] = -1;
int t = 1;
cin >> t;
while (t--) solve();
}
/*
KIVI
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9008kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 2 5 3 6 Yes 2 4 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 247ms
memory: 22904kb
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 139 79 244 202 310 289 322 316 382 337 451 397 463 460 517 481 526 520 568 556 661 619 763 736 853 790 934 904 988 979 1105 1090 1219 1162 1285 1273 1405 1294 1456 1411 1531 1459 1561 1555 1615 1588 1630 1618 1669 1651 1723 1684 1915 1738 2026 1972 2092 2029 2197 2155 2305 2290 2353 2350 2431 24...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 9092kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 41 40 43 42 45 44 47 46 49 48 51 50 53 52 55 54 57 56 39 58 30 29 32 31 34 33 76 75 78 77 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 60 59 62 61 64 63 66 65 68 67 37 36 35 38 3 2 5 4 7 6 1 8 70 69 72 71 74 73 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 223ms
memory: 24888kb
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...
output:
Yes 29330 29329 29332 29331 29334 29333 29336 29335 29338 29337 29340 29339 29342 29341 29344 29343 29346 29345 29348 29347 29350 29349 29352 29351 71755 71754 71757 71756 71759 71758 71761 71760 71763 71762 71765 71764 71767 71766 71769 71768 71771 71770 71773 71772 71775 71774 71777 71776 71779 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 466ms
memory: 19648kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 26518 8564 1121 63463 129 36817 95315 8931 28 89504 81303 70110 16772 13611 778 34736 80993 88310 74032 11544 80608 33052 1661 3199 3633 47380 19162 3408 87006 59542 416 97729 73052 62860 56229 35450 9450 55641 2005 99552 4926 84101 92548 81132 83637 41302 28333 92168 3610 71221 37367 78597 8494...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 151ms
memory: 9216kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 5 3 28 26 38 29 43 41 49 45 68 57 71 70 83 74 112 87 119 118 124 122 129 126 139 134 142 141 146 143 165 151 175 170 178 177 184 183 203 200 208 205 219 212 226 220 257 243 268 266 273 270 277 274 285 284 300 298 313 312 324 323 328 326 335 332 345 339 359 354 365 361 370 366 3...
result:
ok 1000 Cases (1000 test cases)