QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334604 | #5423. Perfect Matching | yllcm | AC ✓ | 1048ms | 19480kb | C++14 | 1.7kb | 2024-02-22 08:48:35 | 2024-02-22 08:48:36 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 2e5 + 10;
int n;
int a[N], vis[N], vm[N];
vector<pii> G[N];
vector<pii> mat;
void dfs(int u, int fid) {
vector<int> V;
for(auto t : G[u]) {
int id = t.FR, v = t.SE;
if(vis[v]) {if(!vm[id] && id != fid)V.pb(id); continue;}
vis[v] = true; dfs(v, id);
if(!vm[id])V.pb(id);
}
if((V.size() & 1) && fid)V.pb(fid);
for(int i = 0; i + 1 < V.size(); i += 2)
vm[V[i]] = vm[V[i + 1]] = true, mat.pb({V[i], V[i + 1]});
return ;
}
void solve() {
n = read();
for(int i = 1; i <= n; i++)a[i] = read();
map<int, int> id[2]; int tot = 0;
for(int i = 1; i <= n; i++) {
if(!id[0].count(i + a[i]))id[0][i + a[i]] = ++tot;
if(!id[1].count(i - a[i]))id[1][i - a[i]] = ++tot;
G[id[0][i + a[i]]].pb({i, id[1][i - a[i]]});
G[id[1][i - a[i]]].pb({i, id[0][i + a[i]]});
}
vector<pii>().swap(mat);
for(int i = 1; i <= tot; i++)if(!vis[i])vis[i] = true, dfs(i, 0);
for(int i = 1; i <= tot; i++) {
vector<pii>().swap(G[i]);
vis[i] = false;
}
for(int i = 1; i <= n; i++)vm[i] = false;
if(mat.size() != n / 2)return puts("No"), void();
puts("Yes");
for(auto t : mat)printf("%d %d\n", t.FR, t.SE);
return ;
}
int main() {
int test = read();
while(test--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8468kb
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 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 307ms
memory: 16684kb
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: 8660kb
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 2 3 4 5 6 7 8 1 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 37 38 35 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 39 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 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 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 356ms
memory: 19480kb
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 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 101 10...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 1048ms
memory: 18376kb
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 1793 47710 63141 55...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 217ms
memory: 8516kb
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 23 22 34 33 48 47 73 72 108 107 128 127 148 147 156 155 180 179 193 192 211 210 261 260 263 262 310 309 319 318 343 342 405 404 407 406 418 417 444 443 456 455 503 502 584 583 600 599 664 663 700 699 705 704 719 718 721 720 728 727 740 739 771 770 858 857 913 912 952 951 963 96...
result:
ok 1000 Cases (1000 test cases)