QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#125200 | #5423. Perfect Matching | savacska | AC ✓ | 1606ms | 57368kb | C++23 | 2.7kb | 2023-07-16 05:24:53 | 2023-07-16 05:24:55 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
int mas[100005];
map <int, int> opa_plus, opa_minus;
int num_plus[100005], num_minus[100005];
vector <pair <int, int> > g[200005];
bool used[200005];
int sz[200005];
set <int> two_times[200005], one_times[200005];
void dfs(int v, int &kol)
{
used[v] = true;
kol += sz[v];
for (const auto &[u, num] : g[v])
if (!used[u])
dfs(u, kol);
return;
}
void build_ans(int v, int pr)
{
used[v] = true;
for (const auto &[u, num] : g[v])
if (!used[u])
build_ans(u, num);
int kol = (int) one_times[v].size() + (int) two_times[v].size();
vector <int> spis;
for (int x : one_times[v]) spis.pb(x);
one_times[v].clear();
for (int x : two_times[v])
{
if (kol % 2 == 0 || x != pr) spis.pb(x);
int sec = num_plus[x] ^ num_minus[x] ^ v;
two_times[sec].erase(x);
}
two_times[v].clear();
if (kol % 2 == 1) one_times[num_plus[pr] ^ num_minus[pr] ^ v].insert(pr);
for (int i = 0; i < (int) spis.size(); i += 2) cout << spis[i] << ' ' << spis[i + 1] << '\n';
return;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int test;
cin >> test;
for (int rep = 1; rep <= test; rep++)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> mas[i];
opa_plus.clear(), opa_minus.clear();
for (int i = 1; i <= n; i++)
{
opa_plus.insert(mp(mas[i] + i, 0));
opa_minus.insert(mp(mas[i] - i, 0));
}
int cnt = 0;
for (auto &[dd, num] : opa_plus)
num = ++cnt;
for (auto &[dd, num] : opa_minus)
num = ++cnt;
for (int i = 1; i <= cnt; i++) g[i].clear(), sz[i] = 0, one_times[i].clear(), two_times[i].clear();
for (int i = 1; i <= n; i++)
{
num_plus[i] = opa_plus[mas[i] + i];
num_minus[i] = opa_minus[mas[i] - i];
g[num_plus[i]].pb(mp(num_minus[i], i));
g[num_minus[i]].pb(mp(num_plus[i], i));
sz[num_plus[i]]++, sz[num_minus[i]]++;
two_times[num_plus[i]].insert(i);
two_times[num_minus[i]].insert(i);
}
bool fl = true;
for (int i = 1; i <= cnt; i++) used[i] = false;
for (int i = 1; i <= cnt; i++)
{
if (!used[i])
{
int kol = 0;
dfs(i, kol);
if (kol / 2 % 2 == 1) fl = false;
}
}
if (!fl) {cout << "No\n"; continue;}
cout << "Yes\n";
for (int i = 1; i <= cnt; i++) used[i] = false;
for (int i = 1; i <= cnt; i++)
{
if (!used[i]) build_ans(i, -1);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 28480kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 5 2 6 3 Yes 4 2 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 1008ms
memory: 49752kb
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 77 78 137 138 200 201 242 244 287 289 308 309 314 315 320 321 335 337 380 382 395 396 449 450 458 459 461 462 479 480 515 517 518 520 524 526 554 556 566 567 617 619 659 660 734 736 761 763 788 790 851 853 902 903 932 933 977 978 986 987 1088 1089 1103 1104 1160 1162 1217 1218 1271 1273 1283 128...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 27924kb
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 39 29 30 31 32 33 34 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 59 60 61 62 63 64 65 66 67 68 36 37 38 35 2 3 4 5 6 7 8 1 69 70 71 72 73 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 617ms
memory: 57368kb
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 29329 29330 29331 29332 29333 29334 29335 29336 29337 29338 29339 29340 29341 29342 29343 29344 29345 29346 29347 29348 29349 29350 29351 29352 71754 71755 71756 71757 71758 71759 71760 71761 71762 71763 71764 71765 71766 71767 71768 71769 71770 71771 71772 71773 71774 71775 71776 71777 71778 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 1606ms
memory: 50760kb
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 89504 28 8564 26518 63463 1121 36811 36817 8931 95315 96991 61541 81132 92548 41302 83637 34736 778 12537 4360 99552 2005 97953 92893 58176 30631 70597 19622 37677 26691 27149 66364 67617 10211 17075 44140 57643 11472 23176 35741 95323 12598 9050 10585 68565 28519 21782 10746 47710 63141 1793 55...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 390ms
memory: 28472kb
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 22 23 33 34 47 48 72 73 107 108 127 128 147 148 155 156 179 180 192 193 210 211 260 261 262 263 309 310 318 319 342 343 404 405 406 407 417 418 443 444 455 456 502 503 583 584 599 600 663 664 699 700 704 705 718 719 720 721 727 728 739 740 770 771 857 858 912 913 951 952 962 96...
result:
ok 1000 Cases (1000 test cases)