QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771750 | #5423. Perfect Matching | cyc001 | WA | 368ms | 26528kb | C++23 | 2.8kb | 2024-11-22 15:25:49 | 2024-11-22 15:25:51 |
Judging History
answer
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
#define fcin cin
#define fcout cout
class tree{
private:
vector<vector<pair<int,int>>> gr;
vector<int> id;
vector<int> sum,siz,vis;
auto dfs(int u,int fr=-1)->void{
sum[u]=siz[u];vis[u]=true;
for(auto&[v,w]:gr[u]) if(!vis[v]){
// cerr<<u<<' '<<v<<' '<<w<<'\n';
dfs(v,u);sum[u]+=(sum[v]-1);
if(sum[v]&1) id[w]=u;
else id[w]=v;
}else{
if(v!=fr) --sum[u];
}
// cerr<<u<<":"<<sum[u]<<'\n';
}
public:
auto link(int u,int v,int w){
gr[u].emplace_back(v,w);
gr[v].emplace_back(u,w);
}
auto setsiz(vector<int> _siz){siz=_siz;}
auto check(){
cir(i,0,(int)(gr.size())) if(!vis[i]) dfs(i);
return id;
}
tree(int _n,int _m):gr(_n),id(_m),sum(_n),siz(_n),vis(_n){}
};
class dsu{
private:
vector<int> f,siz;
public:
auto findset(int u)->int{
return f[u]==u?u:f[u]=findset(f[u]);
}
auto merge(int u,int v){
u=findset(u);v=findset(v);
if(u==v) return;
f[u]=v;siz[v]+=siz[u];
}
auto size(auto u){return siz[findset(u)];}
dsu(int _n):f(_n),siz(_n,1){iota(f.begin(),f.end(),0);}
};
int main(){
ios::sync_with_stdio(false),fcin.tie(nullptr);
int T;fcin>>T;
while(T--) []{
int n;fcin>>n;vector<int> a(n);
for(auto&i:a) fcin>>i;
map<int,vector<int>> ax,bx;
cir(i,0,n) ax[a[i]-i].push_back(i);
cir(i,0,n) bx[a[i]+i].push_back(i);
vector<vector<int>> fr(n);
dsu ds(n);
auto cccnt=-1;
vector<int> siz;
for(auto&[a,b]:ax){
++cccnt;
for(auto&i:b) fr[i].push_back(cccnt);
cir(i,1,(int)(b.size())) ds.merge(b[i-1],b[i]);
siz.push_back(b.size());
}
for(auto&[a,b]:bx){
++cccnt;
for(auto&i:b) fr[i].push_back(cccnt);
cir(i,1,(int)(b.size())) ds.merge(b[i-1],b[i]);
siz.push_back(b.size());
}
auto vaild=true;
cir(i,0,n) vaild&=(!(ds.size(i)&1));
if(!vaild) return fcout<<"No"<<'\n',void();
tree tr(cccnt+1,n);
cir(i,0,n) tr.link(fr[i][0],fr[i][1],i);// ,clog<<fr[i][0]<<' '<<fr[i][1]<<' '<<i<<'\n';
// cir(i,0,cccnt) clog<<siz[i]<<' ';
// clog<<'\n';
// clog.flush();
tr.setsiz(siz);
const auto id=tr.check();
map<int,vector<int>> idx;
cir(i,0,n) idx[id[i]].push_back(i);
fcout<<"Yes"<<'\n';
for(auto&[a,b]:idx){
for(auto i=0;i<(int)(b.size());i+=2) fcout<<b[i]+1<<' '<<b[i+1]+1<<'\n';
}
}();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 2 5 3 6 1 4 Yes 2 4 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 368ms
memory: 26528kb
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 2 3 11 23 29 31 32 36 39 42 46 49 52 54 55 66 68 73 75 77 78 84 88 91 93 95 98 100 106 109 120 122 124 127 128 130 137 138 141 148 150 151 154 156 160 163 166 167 171 174 175 177 179 187 189 190 196 197 200 201 203 207 208 210 213 216 224 226 228 235 237 241 242 245 249 250 255 261 262 265 267 2...
result:
wrong answer abs(32-36) != abs(a[32]-a[36]) (test case 1)