QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#128998 | #5423. Perfect Matching | PetroTarnavskyi# | AC ✓ | 837ms | 38192kb | C++17 | 2.1kb | 2023-07-21 18:45:40 | 2023-07-21 18:45:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int N = 1 << 17;
set<int> nused[N][2];
int used[N];
int x[N], y[N];
vector<PII> ans;
int dfs(int v, int par){
auto& L = nused[x[v]][0];
auto& R = nused[y[v]][1];
used[v] = 1;
L.erase(v);
R.erase(v);
int l = -1;
if(SZ(L) != 0){
int to = *L.begin();
l = dfs(to, v);
}
int r = -1;
if(SZ(R) != 0){
int to = *R.begin();
r = dfs(to, v);
}
if(l == -1 && r == -1)
return v;
if(l == -1){
ans.PB({v, r});
return -1;
}
if(r == -1){
ans.PB({v, l});
return -1;
}
if(par == -1)
return -1;
if(x[v] == x[par]){
ans.PB({v, r});
return l;
}
if(y[v] == y[par]){
ans.PB({v, l});
return r;
}
assert(0);
return -1;
}
void solve(){
int n;
cin >> n;
VI a(n);
FOR(i, 0, n)
{
cin >> a[i];
x[i] = a[i] - i;
y[i] = a[i] + i;
}
VI v(x, x + n);
sort(ALL(v));
FOR (i, 0, n) x[i] = lower_bound(ALL(v), x[i]) - v.begin();
v = VI(y, y + n);
sort(ALL(v));
FOR (i, 0, n) y[i] = lower_bound(ALL(v), y[i]) - v.begin();
FOR(i, 0, n){
used[i] = 0;
nused[x[i]][0].insert(i);
nused[y[i]][1].insert(i);
}
FOR(i, 0, n){
if(used[i])
continue;
dfs(i, -1);
}
if(2 * SZ(ans) != n){
cout << "No\n";
}
else{
cout << "Yes\n";
FOR(i, 0, SZ(ans)){
//assert(x[ans[i].F] == x[ans[i].S] || y[ans[i].F] == y[ans[i].S]);
cout << ans[i].F + 1 << " " << ans[i].S + 1 << "\n";
}
}
ans.clear();
FOR(i, 0, n){
nused[x[i]][0].clear();
nused[y[i]][1].clear();
used[i] = 0;
}
}
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: 5ms
memory: 15828kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 2 5 3 6 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 487ms
memory: 38192kb
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 99823 99979 99930 99981 99939 99993 99893 99927 99872 99890 99935 99983 99812 99923 99770 99794 99722 99725 99698 99704 99638 99671 99584 99626 99494 99548 99479 99485 99413 99464 99398 99410 99383 99392 99374 99377 99266 99329 99230 99248 99125 99215 99077 99092 99041 99059 99023 99026 98966 98...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 15908kb
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 7 8 5 6 3 4 1 2 27 28 25 26 23 24 21 22 19 20 17 18 15 16 13 14 11 12 9 10 33 34 31 32 29 30 37 38 35 36 57 58 55 56 53 54 51 52 49 50 47 48 45 46 43 44 41 42 39 40 67 68 65 66 63 64 61 62 59 60 73 74 71 72 69 70 99 100 97 98 95 96 93 94 91 92 89 90 87 88 85 86 83 84 81 82 79 80 77 78 75 76 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 326ms
memory: 27824kb
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 273 274 271 272 269 270 267 268 265 266 263 264 261 262 259 260 257 258 255 256 253 254 251 252 249 250 247 248 245 246 243 244 241 242 239 240 237 238 235 236 233 234 231 232 229 230 227 228 225 226 223 224 221 222 219 220 217 218 215 216 213 214 211 212 209 210 207 208 205 206 203 204 201 202 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 837ms
memory: 34292kb
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 99438 99509 89492 99574 82608 85048 92652 97510 88495 89905 78226 78629 61827 64315 94056 95227 58552 59227 92602 95172 87927 88726 85123 85436 88825 98959 85966 88659 82426 84374 79221 81195 72039 75869 70397 70561 51532 63374 99488 99601 98732 98890 96424 97093 92713 93146 90576 94256 84380 87...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 286ms
memory: 16544kb
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 986 988 968 982 961 962 957 958 941 951 933 935 901 912 897 898 879 896 866 875 857 862 852 856 833 843 811 823 809 810 803 808 795 799 783 785 775 777 770 774 767 769 758 761 752 755 739 747 730 737 720 727 715 718 704 706 702 703 699 701 670 694 660 663 654 659 646 653 631 63...
result:
ok 1000 Cases (1000 test cases)