QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#650312 | #5423. Perfect Matching | ucup-team3161# | AC ✓ | 492ms | 81800kb | C++17 | 1.3kb | 2024-10-18 14:34:12 | 2024-10-18 14:34:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
const int N=1e6+5;
int T,n,a[N],ds1[N],ds2[N],fa[N],z[N];
vector<pair<int,int>> e[N];vector<int> vc[N];
int find(int u) {return u==fa[u]?u:fa[u]=find(fa[u]);}
bool merge(int u,int v)
{u=find(u);v=find(v);if(u==v) return 0;fa[u]=v;return 1;}
void work(int ds[])
{sort(ds+1,ds+ds[0]+1);ds[0]=unique(ds+1,ds+ds[0]+1)-ds-1;}
int id(int ds[],int x) {return lower_bound(ds+1,ds+ds[0]+1,x)-ds;}
void dfs(int u,int f)
{
for(auto [v,id]:e[u]) if(v!=f)
{dfs(v,u);if(z[v]) z[v]^=1,vc[v].eb(id);else z[u]^=1,vc[u].eb(id);}
}
void slv()
{
scanf("%d",&n);ds1[0]=ds2[0]=0;iota(fa+1,fa+n*2+1,1);fill(z+1,z+n*2+1,0);
for(int i=1;i<=n*2;++i) e[i].clear(),vc[i].clear();
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),ds1[++ds1[0]]=a[i]+i,ds2[++ds2[0]]=a[i]-i;
work(ds1);work(ds2);
for(int i=1,u,v;i<=n;++i)
{
u=id(ds1,a[i]+i);v=n+id(ds2,a[i]-i);
if(merge(u,v)) e[u].eb(v,i),e[v].eb(u,i);else z[u]^=1,vc[u].eb(i);
}
for(int i=1;i<=n*2;++i) if(find(i)==i) {dfs(i,0);if(z[i]) {puts("No");return;}}
puts("Yes");
for(int i=1,t;i<=n*2;++i)
{t=0;for(auto j:vc[i]) {if(t) printf("%d %d\n",j,t),t=0;else t=j;}}
}
int main()
{
scanf("%d",&T);
while(T--) slv();return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 59712kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 5 2 6 3 Yes 3 1 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 254ms
memory: 71944kb
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 107 53 185 152 248 233 317 260 410 368 575 539 707 590 755 737 797 794 809 803 863 815 953 890 1055 1010 1064 1058 1082 1070 1139 1112 1175 1151 1247 1232 1382 1313 1520 1484 1610 1550 1715 1694 1748 1739 1781 1775 1868 1805 1949 1916 2006 1973 2078 2015 2168 2144 2306 2237 2327 2309 2375 2345 2...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 59552kb
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 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 70 69 72 71 74 73 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 36 35 38 37 2 1 4 3 6 5 8 7 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 240ms
memory: 81800kb
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 82228 82227 82230 82229 82232 82231 82234 82233 82236 82235 82238 82237 82240 82239 82242 82241 82244 82243 82246 82245 82248 82247 82250 82249 82252 82...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 492ms
memory: 72704kb
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 32 3 1932 170 3820 1986 5851 5658 7783 5902 8799 8281 9393 9282 10805 9892 13900 13027 17031 15615 20491 18370 22113 20817 31175 23424 32863 32797 37250 34960 38188 38102 39303 39104 45366 45082 56409 47987 59024 58265 62116 61232 65281 62789 71444 65387 76759 76524 78974 77522 80672 79799 82317...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 159ms
memory: 59076kb
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 14 15 22 23 33 34 37 36 47 48 57 59 66 67 72 73 74 75 77 78 98 99 107 108 112 113 127 128 131 130 142 144 147 148 151 152 155 156 161 162 165 167 170 171 179 180 183 185 184 186 192 193 198 199 200 202 205 207 210 211 212 213 214 215 220 221 232 233 243 245 260 261 262 263 266 ...
result:
ok 1000 Cases (1000 test cases)