QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547332 | #5423. Perfect Matching | Wuyanru | AC ✓ | 617ms | 12812kb | C++14 | 2.6kb | 2024-09-04 20:33:21 | 2024-09-04 20:33:23 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
template<const int N,const int M>
struct wgraph
{
int head[N+5];
int ww[M+5];
int t[M+5];
int x[M+5];
int cntm;
wgraph(){ cntm=1;}
inline void clear(int n=N)
{
cntm=1;
for(int i=1;i<=n;i++) head[i]=0;
}
inline void ad(int u,int v,int w)
{
cntm++;
t[cntm]=v;
x[cntm]=head[u];
ww[cntm]=w;
head[u]=cntm;
}
inline void add(int u,int v,int w)
{
// printf("add %d %d %d\n",u,v,w);
ad(u,v,w);
ad(v,u,w);
}
inline int st(int num){ return head[num];}
inline int to(int num){ return t[num];}
inline int nx(int num){ return x[num];}
inline int w(int num){ return ww[num];}
};
wgraph<200000,200000>g;
map<int,int>id1;
map<int,int>id2;
bool dfn[200001];
bool vis[200001];
int a[100001];
vc<pi>ans;
int n,c;
inline void clear()
{
memset(vis,0,sizeof(bool)*(n+1));
memset(dfn,0,sizeof(bool)*(c+1));
g.clear(c);
id1.clear();
id2.clear();
ans.clear();
}
void dfs(int num,int faw)
{
vc<int>son;dfn[num]=1;
for(int i=g.st(num);i;i=g.nx(i))
{
int p=g.to(i);
if(g.w(i)==faw) continue;
if(!dfn[p]) dfs(p,g.w(i));
if(!vis[g.w(i)]) son.push_back(g.w(i));
}
if(son.size()&1) son.push_back(faw);
for(unsigned i=0;i<son.size();i+=2)
{
vis[son[i]]=vis[son[i+1]]=1;
ans.push_back(pi(son[i],son[i+1]));
}
}
inline void solve()
{
clear();n=read(),c=0;
for(int i=1;i<=n;i++)
{
a[i]=read();
if(!id1.count(a[i]-i)) id1[a[i]-i]=++c;
if(!id2.count(a[i]+i)) id2[a[i]+i]=++c;
g.add(id1[a[i]-i],id2[a[i]+i],i);
}
for(int i=1;i<=c;i++) if(!dfn[i]) dfs(i,0);
if((int)ans.size()!=n/2) printf("No\n");
else
{
printf("Yes\n");
for(auto i:ans) printf("%d %d\n",i.first,i.second);
}
}
int main()
{
int T=read();
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6024kb
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: 233ms
memory: 10780kb
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 99977 99979 99821 99823 99980 99981 99929 99930 99994 99993 99940 99939 99928 99927 99894 99893 99892 99891 99873 99872 99985 99983 99937 99935 99925 99923 99814 99812 99796 99795 99772 99771 99727 99725 99724 99723 99706 99704 99700 99699 99673 99671 99640 99638 99628 99627 99586 99584 99550 99...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 5840kb
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 8 7 6 5 4 3 2 1 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 34 33 32 31 30 29 38 37 36 35 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 68 67 66 65 64 63 62 61 60 59 74 73 72 71 70 69 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 249ms
memory: 12812kb
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 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 617ms
memory: 12804kb
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 89930 51424 90797 40204 84293 82260 81601 68474 63426 23563 81768 79940 89209 65068 78623 77535 71925 42616 50015 45416 63727 61582 94113 64578 71688 55765 87755 74925 86349 67712 97794 89613 98375 83954 85705 76781 96630 92136 62221 59568 77914 65037 64568 98085 91652 77633 93510 91261 75990 75...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 137ms
memory: 6096kb
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 987 986 963 962 952 951 913 912 858 857 771 770 740 739 728 727 721 720 719 718 705 704 700 699 664 663 600 599 584 583 503 502 456 455 444 443 418 417 407 406 405 404 343 342 319 318 310 309 263 262 261 260 211 210 193 192 180 179 156 155 148 147 128 127 108 107 73 72 48 47 34...
result:
ok 1000 Cases (1000 test cases)