QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#744023#5423. Perfect Matchingbinbin_200811AC ✓1000ms37688kbC++142.2kb2024-11-13 20:36:582024-11-13 20:37:01

Judging History

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

  • [2024-11-13 20:37:01]
  • 评测
  • 测评结果:AC
  • 用时:1000ms
  • 内存:37688kb
  • [2024-11-13 20:36:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fi first
#define se second

const int maxn=4e5+5;

int n,m,cnt;
int a[maxn];

bool flg;
bool vis[maxn],blk[maxn];

map<int,int>mp[2];

vector<pii>E[maxn];

pii cho[maxn];

inline void clr()
{
    memset(cho,0,sizeof(cho));
    memset(vis,0,sizeof(vis));
    memset(blk,0,sizeof(blk));
    memset(a,0,sizeof(a));
    for(int i=1;i<=m;i++) E[i].clear();
    mp[0].clear();mp[1].clear();
    m=n=cnt=flg=0;
}
inline void sayno()
{
    puts("No");
    flg=1;
    return ;
}

inline void dfs(int u,int id)
{
    vis[u]=1;
    for(auto v:E[u])
    {
        if(!vis[v.fi])
        {
            dfs(v.fi,v.se);
            if(flg) return ;
        }
    }
    vector<int>tmp;
    tmp.clear();
    for(auto v:E[u])
    {
        if(!blk[v.se]&&v.se!=id)
        {
            tmp.push_back(v.se);
        }
    }
    if(tmp.size()&1)
    {
        if(id==0) sayno();
        tmp.push_back(id);
    }
    for(int i=0;i<tmp.size();i+=2) cho[++cnt]={tmp[i],tmp[i+1]},blk[tmp[i]]=blk[tmp[i+1]]=1;
}

int main()
{
    // freopen("matching1.in","r",stdin);
    // freopen("matching.out","w",stdout);
    int _;
    scanf("%d",&_);
    while(_--)
    {
        clr();
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),mp[0][a[i]-i]=1,mp[1][a[i]+i]=1;
        for(int i=0;i<=1;i++)
        {
            auto it1=mp[i].begin(),it2=mp[i].begin();
            for(it2++;it2!=mp[i].end();it1++,it2++) it2->second+=it1->second;
            for(it1=mp[i].begin();it1!=mp[i].end();it1++) it1->second+=m;
            it1--;
            m=it1->second;
        }
        for(int i=1;i<=n;i++)
        {
            E[mp[0][a[i]-i]].push_back({mp[1][a[i]+i],i});
            E[mp[1][a[i]+i]].push_back({mp[0][a[i]-i],i});
            // printf("%d %d\n", mp[0][a[i]-i],mp[1][a[i]+i]);
        }
        for(int i=1;i<=m;i++)
        {
            if(!vis[i]) dfs(i,0);
            if(flg) break;
        }
        if(flg) continue;
        if(cnt!=n/2) sayno();
        if(flg) continue;
        puts("Yes");
        for(int i=1;i<=cnt;i++) printf("%d %d\n",cho[i].fi,cho[i].se);
    }
}

详细

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 408ms
memory: 33988kb

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
77 78
137 138
200 201
242 244
287 289
308 309
314 315
320 321
335 337
380 382
395 396
449 450
458 459
461 462
479 480
515 517
518 520
524 526
554 556
566 567
617 619
659 660
734 736
761 763
788 790
851 853
902 903
932 933
977 978
986 987
1088 1089
1103 1104
1160 1162
1217 1218
1271 1273
1283 128...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 18628kb

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
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
29 30
31 32
33 34
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
59 60
61 62
63 64
65 66
67 68
35 36
37 38
1 2
3 4
5 6
7 8
69 70
71 72
73 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 445ms
memory: 37688kb

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
29329 29330
29331 29332
29333 29334
29335 29336
29337 29338
29339 29340
29341 29342
29343 29344
29345 29346
29347 29348
29349 29350
29351 29352
71753 71754
71755 71756
71757 71758
71759 71760
71761 71762
71763 71764
71765 71766
71767 71768
71769 71770
71771 71772
71773 71774
71775 71776
71777 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 1000ms
memory: 30460kb

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
8564 26518
63463 1121
36811 36817
8931 95315
89504 28
70110 81303
13611 16772
34736 778
80784 80963
88310 80993
821 11544
74032 940
33052 80608
3199 1661
47380 3633
18933 19162
3408 59542
87006 97729
62860 73052
35450 56229
4174 4426
55641 9450
99552 2005
62471 66637
84101 4926
81132 92548
41302...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 460ms
memory: 19028kb

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
15 14
59 57
75 74
113 112
130 131
144 142
152 151
167 165
171 170
185 183
186 184
202 200
207 205
213 212
221 220
245 243
267 266
271 272
278 277
286 284
314 312
330 328
333 334
372 370
377 376
401 400
422 423
426 424
442 440
466 464
476 474
501 499
515 513
559 557
580 578
589 ...

result:

ok 1000 Cases (1000 test cases)