QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#732276#5423. Perfect MatchingyanziheAC ✓562ms89416kbC++145.4kb2024-11-10 13:51:222024-11-10 13:51:24

Judging History

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

  • [2024-11-10 13:51:24]
  • 评测
  • 测评结果:AC
  • 用时:562ms
  • 内存:89416kb
  • [2024-11-10 13:51:22]
  • 提交

answer

//幽默题
/*
思路1:
转平面直角坐标系,贯穿于同一根45度斜线的点相互连边

思路2:
拆绝对值
红边:若干个团
蓝边:若干个团
不存在重合的红边和蓝边
每个点有红色数字和蓝色数字
不存在两个红色数字和蓝数都相同的点
有若干个组,每组中选择奇数/偶数个点,让它们可以两两匹配

树链剖分我们喜欢你
*/
#include <bits/stdc++.h>//幽默题
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=a;i<=b;i++)
#define rrep(i, a, b) for(ll i=a;i>=b;i--)
const ll N=5e5+9;
ll T, n, a[N];
struct point{
    ll red, blue, id;
    bool operator<(const point &b)const{
        return red<b.red||red==b.red&&blue<b.blue;
    }
}p[N];
ll bred[N], bblue[N],nR, nB;
bool vst[N], vot[N];
ll cnt[N];//cnt[i]表示红色为i的点有多少个
vector <ll> roast[N], tog[N], tot[N];
vector <pair<ll, ll> > pog[N];//po表示一条边对应的是那两个点之间的抵消
pair <ll, ll> po[N];//po[i]表示i和它父亲的这一条边
void dfs_findtree(ll u){
    vst[u]=1;
    for(ll i=0;i<tog[u].size();i++){ll v=tog[u][i];
        if(vst[v])continue;
        tot[u].emplace_back(v);
        tot[v].emplace_back(u);
        po[v].first=pog[u][i].first;
        po[v].second=pog[u][i].second;

        dfs_findtree(v);
    }    
}
ll need[N];
ll inblue[N];
bool dfs_solve(ll u, ll fa){//返回又没有剩余
    // cout << 'u' << u << '\n';
    vot[u]=1;
    ll lastfail=0;
    for(ll v:tot[u]){
        if(v==fa)continue;
        bool x=dfs_solve(v, u);
        if(x){
            if(lastfail==0)lastfail=v;
            else {need[v]^=1;need[lastfail]^=1;lastfail=0;}
        }
    }
    if(cnt[u]&1){
        if(lastfail==0)return 1;
        else {need[lastfail]^=1;return 0;}
    }else{
        if(lastfail==0)return 0;
        else {need[lastfail]^=1;return 1;}
    }
}
void clear(){
    fill(need, need+n+5, 0);
    fill(inblue, inblue+n+5, 0);
    fill(bred, bred+n+5, 0);
    fill(bblue, bblue+n+5, 0);
    fill(vst, vst+n+5, 0);
    fill(vot, vot+n+5, 0);
    nR=0;nB=0;
    fill(cnt, cnt+n+5, 0);
    rep(i, 1, n+3){
        roast[i].clear();
        tog[i].clear();

        tot[i].clear();

        pog[i].clear();

        po[i]=make_pair(0, 0);

    }
}
int main(){
 //   freopen("matching.in", "r", stdin);
  //  freopen("matching.out", "w", stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--){
        cin >> n;
        rep(i, 1, n){
            cin >> a[i];
            p[i].red=i-a[i];
            p[i].blue=i+a[i];
            p[i].id=i;
            bred[i]=p[i].red;
            bblue[i]=p[i].blue;
        }
        sort(bred+1, bred+n+1);
        nR=unique(bred+1, bred+n+1)-(bred+1);
        sort(bblue+1, bblue+n+1);
        nB=unique(bblue+1, bblue+n+1)-(bblue+1);
        rep(i, 1, n){
            p[i].red=lower_bound(bred+1, bred+nR+1, p[i].red)-bred;
            p[i].blue=lower_bound(bblue+1, bblue+nB+1, p[i].blue)-bblue;
            // cout << p[i].red << ' ' << p[i].blue << '\n';
        }
        sort(p+1, p+n+1);
        rep(i, 1, n){
            cnt[p[i].red]++;
            roast[p[i].blue].emplace_back(i);
            // cout << i << "is in " << p[i].blue << endl;
        }
        // rep(i, 1, nR){
        //     cout << i << ' ' << cnt[i] << endl;
        // }
        rep(i, 1, nB){
            for(ll j=1;j<roast[i].size();j++){
                // cout << "in" << i << ' ' << roast[i][j] << '\n';
                tog[p[roast[i][j-1]].red].emplace_back(p[roast[i][j]].red);
                tog[p[roast[i][j]].red].emplace_back(p[roast[i][j-1]].red);
                pog[p[roast[i][j-1]].red].emplace_back(make_pair(roast[i][j-1], roast[i][j]));
                pog[p[roast[i][j]].red].emplace_back(make_pair(roast[i][j-1], roast[i][j]));
            }
        }
        rep(i, 1, nR){
            if(!vst[i]){
                dfs_findtree(i);
            }
        }
        bool ok=1;
        rep(i, 1, nR){
            if(!vot[i])
            if(dfs_solve(i, 0)){
                ok=0;break;
            }
            // cout << '\n';
        }
        if(ok==0){
            cout << "No" << '\n';
        }else{
            cout << "Yes" << '\n';
            rep(i, 1, nR){
                // cout << need[i] << '/';
                if(need[i]){
                    inblue[po[i].first]^=1;
                    inblue[po[i].second]^=1;
                }
            }
            // cout << '\n';
            // rep(i, 1, n){
            //     cout << inblue[i] << '|';
            // }
            // cout << '\n';
            rep(i, 1, nB){
                ll lastib=0;
                for(ll j=0;j<roast[i].size();j++){
                    ll u=roast[i][j];
                    if(inblue[u]){
                        if(lastib==0)lastib=u;
                        else {cout << p[lastib].id << ' ' << p[u].id << '\n';lastib=0;}
                    }
                }
            }
            ll lastd=0;
            rep(i, 1, n){
                if(p[i].red!=p[i-1].red){
                    lastd=0;
                }
                if(!inblue[i]){
                    if(lastd==0)lastd=i;
                    else {cout << p[lastd].id << ' ' << p[i].id << '\n';lastd=0;}
                }
            }
        }
        clear();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 10ms
memory: 65116kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 332ms
memory: 84400kb

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
50 53
248 260
317 368
539 575
794 797
803 815
953 1055
1058 1064
1070 1082
1139 1151
1247 1313
1520 1610
1739 1781
1868 1916
1949 2078
2144 2237
2309 2345
2375 2414
2420 2423
2606 2627
2723 2789
2792 2822
2867 2981
3002 3119
3149 3191
3389 3398
3410 3461
3476 3503
3506 3512
3530 3533
3548 3611
3...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 8ms
memory: 65056kb

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
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
69 70
71 72
73 74
1 2
3 4
5 6
7 8
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 255ms
memory: 89416kb

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
82227 82228
82229 82230
82231 82232
82233 82234
82235 82236
82237 82238
82239 82240
82241 82242
82243 82244
82245 82246
82247 82248
82249 82250
82251 82...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 562ms
memory: 87584kb

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
1 32
49 1575
1932 1986
2760 3820
5658 5750
5902 7783
8281 8799
9282 9343
9393 9892
13027 13900
14383 15170
17031 18370
20491 20817
22113 23424
24908 31175
32797 34960
39303 45082
48975 56409
59024 61232
62116 71444
76524 76759
78974 79799
80672 84250
93166 98041
99492 99604
15 39
111 254
265 413...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 193ms
memory: 65256kb

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
3 5
26 28
29 36
38 41
43 45
49 57
68 70
71 74
83 87
112 118
119 122
124 126
129 134
139 141
142 143
146 151
165 170
175 177
178 183
184 200
203 205
208 212
219 220
226 243
257 266
268 270
273 274
277 284
285 298
300 312
313 323
324 326
328 332
335 339
345 354
359 361
365 366
37...

result:

ok 1000 Cases (1000 test cases)