QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#732276 | #5423. Perfect Matching | yanzihe | AC ✓ | 562ms | 89416kb | C++14 | 5.4kb | 2024-11-10 13:51:22 | 2024-11-10 13:51:24 |
Judging History
answer
//幽默题
/*
思路1:
转平面直角坐标系,贯穿于同一根45度斜线的点相互连边
思路2:
拆绝对值
红边:若干个团
蓝边:若干个团
不存在重合的红边和蓝边
每个点有红色数字和蓝色数字
不存在两个红色数字和蓝数都相同的点
有若干个组,每组中选择奇数/偶数个点,让它们可以两两匹配
树链剖分我们喜欢你
*/
#include <bits/stdc++.h>//幽默题
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=a;i<=b;i++)
#define rrep(i, a, b) for(ll i=a;i>=b;i--)
const ll N=5e5+9;
ll T, n, a[N];
struct point{
ll red, blue, id;
bool operator<(const point &b)const{
return red<b.red||red==b.red&&blue<b.blue;
}
}p[N];
ll bred[N], bblue[N],nR, nB;
bool vst[N], vot[N];
ll cnt[N];//cnt[i]表示红色为i的点有多少个
vector <ll> roast[N], tog[N], tot[N];
vector <pair<ll, ll> > pog[N];//po表示一条边对应的是那两个点之间的抵消
pair <ll, ll> po[N];//po[i]表示i和它父亲的这一条边
void dfs_findtree(ll u){
vst[u]=1;
for(ll i=0;i<tog[u].size();i++){ll v=tog[u][i];
if(vst[v])continue;
tot[u].emplace_back(v);
tot[v].emplace_back(u);
po[v].first=pog[u][i].first;
po[v].second=pog[u][i].second;
dfs_findtree(v);
}
}
ll need[N];
ll inblue[N];
bool dfs_solve(ll u, ll fa){//返回又没有剩余
// cout << 'u' << u << '\n';
vot[u]=1;
ll lastfail=0;
for(ll v:tot[u]){
if(v==fa)continue;
bool x=dfs_solve(v, u);
if(x){
if(lastfail==0)lastfail=v;
else {need[v]^=1;need[lastfail]^=1;lastfail=0;}
}
}
if(cnt[u]&1){
if(lastfail==0)return 1;
else {need[lastfail]^=1;return 0;}
}else{
if(lastfail==0)return 0;
else {need[lastfail]^=1;return 1;}
}
}
void clear(){
fill(need, need+n+5, 0);
fill(inblue, inblue+n+5, 0);
fill(bred, bred+n+5, 0);
fill(bblue, bblue+n+5, 0);
fill(vst, vst+n+5, 0);
fill(vot, vot+n+5, 0);
nR=0;nB=0;
fill(cnt, cnt+n+5, 0);
rep(i, 1, n+3){
roast[i].clear();
tog[i].clear();
tot[i].clear();
pog[i].clear();
po[i]=make_pair(0, 0);
}
}
int main(){
// freopen("matching.in", "r", stdin);
// freopen("matching.out", "w", stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> T;
while(T--){
cin >> n;
rep(i, 1, n){
cin >> a[i];
p[i].red=i-a[i];
p[i].blue=i+a[i];
p[i].id=i;
bred[i]=p[i].red;
bblue[i]=p[i].blue;
}
sort(bred+1, bred+n+1);
nR=unique(bred+1, bred+n+1)-(bred+1);
sort(bblue+1, bblue+n+1);
nB=unique(bblue+1, bblue+n+1)-(bblue+1);
rep(i, 1, n){
p[i].red=lower_bound(bred+1, bred+nR+1, p[i].red)-bred;
p[i].blue=lower_bound(bblue+1, bblue+nB+1, p[i].blue)-bblue;
// cout << p[i].red << ' ' << p[i].blue << '\n';
}
sort(p+1, p+n+1);
rep(i, 1, n){
cnt[p[i].red]++;
roast[p[i].blue].emplace_back(i);
// cout << i << "is in " << p[i].blue << endl;
}
// rep(i, 1, nR){
// cout << i << ' ' << cnt[i] << endl;
// }
rep(i, 1, nB){
for(ll j=1;j<roast[i].size();j++){
// cout << "in" << i << ' ' << roast[i][j] << '\n';
tog[p[roast[i][j-1]].red].emplace_back(p[roast[i][j]].red);
tog[p[roast[i][j]].red].emplace_back(p[roast[i][j-1]].red);
pog[p[roast[i][j-1]].red].emplace_back(make_pair(roast[i][j-1], roast[i][j]));
pog[p[roast[i][j]].red].emplace_back(make_pair(roast[i][j-1], roast[i][j]));
}
}
rep(i, 1, nR){
if(!vst[i]){
dfs_findtree(i);
}
}
bool ok=1;
rep(i, 1, nR){
if(!vot[i])
if(dfs_solve(i, 0)){
ok=0;break;
}
// cout << '\n';
}
if(ok==0){
cout << "No" << '\n';
}else{
cout << "Yes" << '\n';
rep(i, 1, nR){
// cout << need[i] << '/';
if(need[i]){
inblue[po[i].first]^=1;
inblue[po[i].second]^=1;
}
}
// cout << '\n';
// rep(i, 1, n){
// cout << inblue[i] << '|';
// }
// cout << '\n';
rep(i, 1, nB){
ll lastib=0;
for(ll j=0;j<roast[i].size();j++){
ll u=roast[i][j];
if(inblue[u]){
if(lastib==0)lastib=u;
else {cout << p[lastib].id << ' ' << p[u].id << '\n';lastib=0;}
}
}
}
ll lastd=0;
rep(i, 1, n){
if(p[i].red!=p[i-1].red){
lastd=0;
}
if(!inblue[i]){
if(lastd==0)lastd=i;
else {cout << p[lastd].id << ' ' << p[i].id << '\n';lastd=0;}
}
}
}
clear();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 65116kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 3 6 2 5 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 332ms
memory: 84400kb
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 50 53 248 260 317 368 539 575 794 797 803 815 953 1055 1058 1064 1070 1082 1139 1151 1247 1313 1520 1610 1739 1781 1868 1916 1949 2078 2144 2237 2309 2345 2375 2414 2420 2423 2606 2627 2723 2789 2792 2822 2867 2981 3002 3119 3149 3191 3389 3398 3410 3461 3476 3503 3506 3512 3530 3533 3548 3611 3...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 8ms
memory: 65056kb
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 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 69 70 71 72 73 74 1 2 3 4 5 6 7 8 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 255ms
memory: 89416kb
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 82227 82228 82229 82230 82231 82232 82233 82234 82235 82236 82237 82238 82239 82240 82241 82242 82243 82244 82245 82246 82247 82248 82249 82250 82251 82...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 562ms
memory: 87584kb
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 1 32 49 1575 1932 1986 2760 3820 5658 5750 5902 7783 8281 8799 9282 9343 9393 9892 13027 13900 14383 15170 17031 18370 20491 20817 22113 23424 24908 31175 32797 34960 39303 45082 48975 56409 59024 61232 62116 71444 76524 76759 78974 79799 80672 84250 93166 98041 99492 99604 15 39 111 254 265 413...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 193ms
memory: 65256kb
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 3 5 26 28 29 36 38 41 43 45 49 57 68 70 71 74 83 87 112 118 119 122 124 126 129 134 139 141 142 143 146 151 165 170 175 177 178 183 184 200 203 205 208 212 219 220 226 243 257 266 268 270 273 274 277 284 285 298 300 312 313 323 324 326 328 332 335 339 345 354 359 361 365 366 37...
result:
ok 1000 Cases (1000 test cases)