QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394193#5423. Perfect MatchingmarherAC ✓530ms10524kbC++141.5kb2024-04-20 10:01:362024-04-20 10:01:37

Judging History

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

  • [2024-04-20 10:01:37]
  • 评测
  • 测评结果:AC
  • 用时:530ms
  • 内存:10524kb
  • [2024-04-20 10:01:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;

struct edge
{
    int u,v,nxt,w,p;
}e[N];

int T,n,a[N],wa[N],wb[N],ma,mb,head[N],cnt=1,vis[N];
vector<pair<int,int>>ans;

void clear()
{
    for(int i=1;i<=ma+mb;i++)head[i]=vis[i]=0;
    cnt=1;vector<pair<int,int>>().swap(ans);
}

void add(int u,int v,int w)
{
    // cout<<u<<' '<<v<<' '<<w<<'\n';
    e[++cnt]=(edge){u,v,head[u],w,0};head[u]=cnt;
    e[++cnt]=(edge){v,u,head[v],w,0};head[v]=cnt;
}

void ad(int x,int y)
{
    ans.push_back(make_pair(e[x].w,e[y].w));
}

int dfs(int x,int fid)
{
    // cout<<"DFS "<<x<<'\n';
    int la=0;vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt)if(!e[i].p)
    {
        e[i].p=e[i^1].p=1;
        int w=0;
        if(!vis[e[i].v])w=dfs(e[i].v,i);
        if(w)continue;
        if(!la)la=i;else ad(la,i),la=0;
    }
    if(la)ad(la,fid);
    // cout<<x<<' '<<fid<<' '<<la<<'\n';
    return la!=0;
}

void sol()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)wa[i]=i-a[i],wb[i]=i+a[i];
    sort(wa+1,wa+1+n);ma=unique(wa+1,wa+1+n)-wa-1;
    sort(wb+1,wb+1+n);mb=unique(wb+1,wb+1+n)-wb-1;
    for(int i=1;i<=n;i++)add(lower_bound(wa+1,wa+1+ma,i-a[i])-wa,lower_bound(wb+1,wb+1+mb,i+a[i])-wb+ma,i);
    for(int i=1;i<=ma;i++)if(!vis[i]&&dfs(i,-1))
    {
        puts("No");
        return;
    }
    puts("Yes");
    for(auto x:ans)cout<<x.first<<' '<<x.second<<'\n';
}

main()
{
    // freopen("in.txt","r",stdin);
    cin>>T;
    while(T--)sol(),clear();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3716kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
6 3
5 2
4 1
Yes
3 1
4 2
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 348ms
memory: 9584kb

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
99871 99869
99890 99870
99864 99863
99850 99849
99831 99830
99796 99794
99792 99791
99790 99789
99795 99788
99772 99770
99754 99753
99771 99752
99751 99750
99724 99722
99718 99...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3648kb

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
74 73
72 71
70 69
8 7
6 5
4 3
2 1
38 37
36 35
68 67
66 65
64 63
62 61
60 59
28 27
26 25
24 23
22 21
20 19
18 17
16 15
14 13
12 11
10 9
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
34 33
32 31
30 29
58 57
56 55
54 53
52 51
50 49
48 47
46 45
44 43
42 41
40 39
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 390ms
memory: 9844kb

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
49560 49559
29398 29397
29396 29395
29394 29393
29392 29391
29390 29389
29388 29387
29386 29385
29384 29383
29382 29381
29380 29379
29378 29377
29376 29375
29374 29373
29372 29371
29370 29369
29368 29367
29366 29365
29364 29363
29362 29361
29360 29359
29358 29357
29356 29355
29354 29353
34124 34...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 530ms
memory: 10524kb

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
99509 99438
99574 89492
85048 82608
95716 94006
92758 87144
86775 86089
95018 90292
96405 38165
98496 86372
75387 52229
89930 51424
72714 64229
83039 60060
93907 59825
90797 40204
84293 82260
81601 68474
98409 66518
90682 86864
63426 23563
97115 55593
98299 86138
81768 79940
78538 71812
70984 66...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 215ms
memory: 3744kb

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
979 981
978 980
994 977
999 998
996 992
985 983
971 965
964 959
945 944
954 936
931 932
930 929
922 921
917 918
915 914
906 894
893 889
886 884
888 885
882 881
883 880
878 877
876 873
860 859
861 849
847 846
845 842
841 839
840 838
837 812
805 804
797 798
793 792
790 791
802 78...

result:

ok 1000 Cases (1000 test cases)