QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771750#5423. Perfect Matchingcyc001WA 368ms26528kbC++232.8kb2024-11-22 15:25:492024-11-22 15:25:51

Judging History

This is the latest submission verdict.

  • [2024-11-22 15:25:51]
  • Judged
  • Verdict: WA
  • Time: 368ms
  • Memory: 26528kb
  • [2024-11-22 15:25:49]
  • Submitted

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)