QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#744023 | #5423. Perfect Matching | binbin_200811 | AC ✓ | 1000ms | 37688kb | C++14 | 2.2kb | 2024-11-13 20:36:58 | 2024-11-13 20:37:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn=4e5+5;
int n,m,cnt;
int a[maxn];
bool flg;
bool vis[maxn],blk[maxn];
map<int,int>mp[2];
vector<pii>E[maxn];
pii cho[maxn];
inline void clr()
{
memset(cho,0,sizeof(cho));
memset(vis,0,sizeof(vis));
memset(blk,0,sizeof(blk));
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++) E[i].clear();
mp[0].clear();mp[1].clear();
m=n=cnt=flg=0;
}
inline void sayno()
{
puts("No");
flg=1;
return ;
}
inline void dfs(int u,int id)
{
vis[u]=1;
for(auto v:E[u])
{
if(!vis[v.fi])
{
dfs(v.fi,v.se);
if(flg) return ;
}
}
vector<int>tmp;
tmp.clear();
for(auto v:E[u])
{
if(!blk[v.se]&&v.se!=id)
{
tmp.push_back(v.se);
}
}
if(tmp.size()&1)
{
if(id==0) sayno();
tmp.push_back(id);
}
for(int i=0;i<tmp.size();i+=2) cho[++cnt]={tmp[i],tmp[i+1]},blk[tmp[i]]=blk[tmp[i+1]]=1;
}
int main()
{
// freopen("matching1.in","r",stdin);
// freopen("matching.out","w",stdout);
int _;
scanf("%d",&_);
while(_--)
{
clr();
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),mp[0][a[i]-i]=1,mp[1][a[i]+i]=1;
for(int i=0;i<=1;i++)
{
auto it1=mp[i].begin(),it2=mp[i].begin();
for(it2++;it2!=mp[i].end();it1++,it2++) it2->second+=it1->second;
for(it1=mp[i].begin();it1!=mp[i].end();it1++) it1->second+=m;
it1--;
m=it1->second;
}
for(int i=1;i<=n;i++)
{
E[mp[0][a[i]-i]].push_back({mp[1][a[i]+i],i});
E[mp[1][a[i]+i]].push_back({mp[0][a[i]-i],i});
// printf("%d %d\n", mp[0][a[i]-i],mp[1][a[i]+i]);
}
for(int i=1;i<=m;i++)
{
if(!vis[i]) dfs(i,0);
if(flg) break;
}
if(flg) continue;
if(cnt!=n/2) sayno();
if(flg) continue;
puts("Yes");
for(int i=1;i<=cnt;i++) printf("%d %d\n",cho[i].fi,cho[i].se);
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 18636kb
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 2 4 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 408ms
memory: 33988kb
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: 18628kb
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 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 35 36 37 38 1 2 3 4 5 6 7 8 69 70 71 72 73 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 445ms
memory: 37688kb
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 71753 71754 71755 71756 71757 71758 71759 71760 71761 71762 71763 71764 71765 71766 71767 71768 71769 71770 71771 71772 71773 71774 71775 71776 71777 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 1000ms
memory: 30460kb
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 8564 26518 63463 1121 36811 36817 8931 95315 89504 28 70110 81303 13611 16772 34736 778 80784 80963 88310 80993 821 11544 74032 940 33052 80608 3199 1661 47380 3633 18933 19162 3408 59542 87006 97729 62860 73052 35450 56229 4174 4426 55641 9450 99552 2005 62471 66637 84101 4926 81132 92548 41302...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 460ms
memory: 19028kb
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 15 14 59 57 75 74 113 112 130 131 144 142 152 151 167 165 171 170 185 183 186 184 202 200 207 205 213 212 221 220 245 243 267 266 271 272 278 277 286 284 314 312 330 328 333 334 372 370 377 376 401 400 422 423 426 424 442 440 466 464 476 474 501 499 515 513 559 557 580 578 589 ...
result:
ok 1000 Cases (1000 test cases)