QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#547330#5423. Perfect MatchingWuyanruRE 212ms10364kbC++142.6kb2024-09-04 20:32:412024-09-04 20:32:41

Judging History

你现在查看的是最新测评结果

  • [2024-09-04 20:32:41]
  • 评测
  • 测评结果:RE
  • 用时:212ms
  • 内存:10364kb
  • [2024-09-04 20:32:41]
  • 提交

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
...

result: