QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547330 | #5423. Perfect Matching | Wuyanru | RE | 212ms | 10364kb | C++14 | 2.6kb | 2024-09-04 20:32:41 | 2024-09-04 20:32:41 |
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[100001];
bool vis[100001];
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: 1ms
memory: 5752kb
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: 212ms
memory: 10364kb
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: 0ms
memory: 6100kb
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: -100
Runtime Error
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 ...