QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334027#8055. Balancewtz2333AC ✓388ms50788kbC++177.1kb2024-02-21 00:42:412024-02-21 00:42:41

Judging History

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

  • [2024-02-21 00:42:41]
  • 评测
  • 测评结果：AC
  • 用时：388ms
  • 内存：50788kb
查看
  • [2024-02-21 00:42:41]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 7;
std::vector<pair<int,int>> e[maxn];
std::vector<int> c[maxn];
int dfn[maxn],low[maxn];
int bel[maxn],bel_siz[maxn];
int s[maxn],cnt,top,tot;
std::vector<vector<int>> ans;
void form(int x){
    int now = 0;
    tot ++;
    do{
        now = s[top --];
        bel[now] = tot;
        bel_siz[tot] ++;
        c[tot].push_back(now);
    }while(now != x);
}
void tarjan(int x,int now){
    dfn[x] = low[x] = ++cnt;
    s[++ top] = x;
    for(auto [v,_]:e[x]){
        if(_ == now)continue;
        if(!dfn[v]){
            tarjan(v,_);
            low[x] = min(low[x],low[v]);
            if(low[v] > dfn[x]){
                form(v);
            }

        }else low[x] = min(low[x],dfn[v]);
    }
}

void clear(int x){
    cnt = tot = top = 0;
    for(int i = 1;i <= x;i ++){
        s[i] = bel[i] = dfn[i] = low[i] = bel_siz[i] = 0;
        e[i].clear();
        c[i].clear();
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T --){
        int n,m;
        cin >> n >> m;
        clear(n);
        for(int i = 1;i <= m;i ++){
            int u,v;
            cin >> u >> v;
            e[u].push_back({v,i});
            e[v].push_back({u,i});
        }
        for(int i = 1;i <= n;i ++){
            if(dfn[i] == 0){
                tarjan(i,0);
                form(i);
            }
        }

        int nn = tot;

        vector<vector<int>> g(n + 1);

        for(int i = 1;i <= n;i ++){
            for(auto [v,_]:e[i]){
                if(bel[i] != bel[v]){
                    g[bel[i]].push_back(bel[v]);
                }
            }
        }

        vector<int> a(n),b,p(n + 1);
        std::vector<int> cnta(n + 1);
        for(int i = 0;i < n;i ++) {
            cin >> a[i];
            cnta[a[i]] ++;
        }
        sort(a.begin(),a.end());
        for(int i = 0;i < n;i ++) {
            p[a[i]] = i + 1;
        }
        b = a;
        reverse(b.begin(),b.end());
        

        vector<array<int,2>> dp(nn + 1),dp_from(nn + 1);
        vector<int> siz(nn + 1),f(nn + 1);

        auto dfs = [&](auto self,int x,int fa) -> void {
            siz[x] = bel_siz[x];
            f[x] = fa;
            for(auto v:g[x]){
                if(v == fa)continue;
                self(self,v,x);
                siz[x] += siz[v];
            }
            for(auto v:g[x]){ // low -> high
                if(v == fa)continue;
                if(dp[v][0]){
                    int val1 = a[siz[v]];
                    int val2 = a[siz[x] - 1];
                    if(val1 == val2){
                        dp[x][0] = 1;
                        dp_from[x][0] = v;
                    }
                }
            }
            for(auto v:g[x]){ // high -> low
                if(v == fa)continue;
                if(dp[v][1]){
                    int val1 = b[siz[v]];
                    int val2 = b[siz[x] - 1];
                    if(val1 == val2){
                        dp[x][1] = 1;
                        dp_from[x][1] = v;
                    }
                }
            }
            dp[x][0] = cnta[a[0]] >= siz[x] ? 1 : dp[x][0];
            dp[x][1] = cnta[b[0]] >= siz[x] ? 1 : dp[x][1];
            // cerr << x << " "<< siz[x] << " " << dp[x][0] << " " << dp[x][1] << "\n";
        };
        dfs(dfs,1,0);
        cerr << nn << "\n";
        std::vector<int> vis(nn + 1);
        int ls = -1,rs = -1;
        int flag = 0;
        for(int i = 1;i <= nn;i ++){
            std::vector<pair<int,int>> tmp;
            for(auto v:g[i]){
                if(v == f[i])continue;
                if(dp[v][1]){
                    tmp.push_back({siz[v],v});
                }
            }
            sort(tmp.begin(),tmp.end());
            for(auto v:g[i]){
                if(v == f[i])continue;
                if(dp[v][0]){
                    int val = a[siz[v]];
                    int rev = p[val] - siz[v];
                    pair<int,int> other = {n - siz[v] - rev,0};
                    auto t = lower_bound(tmp.begin(),tmp.end(),other);
                    // cerr << i << " " << v << " " << rev << " " << siz[v] << "\n";
                    if(t != tmp.end()){
                        if(t->second == v){
                            t ++;
                        }
                        if(t != tmp.end()){
                            ls = v;
                            rs = t->second;
                            flag = 1;
                            break;
                        }
                    }
                }
            }
            if(flag)break;
        }
        // for(int i = 1;i <= n;i ++)cerr << bel[i] << " \n"[i == n];
        if(dp[1][0])flag = 1,ls = 1,rs = -1;
        if(dp[1][1])flag = 1,ls = -1,rs = 1;
        if(flag){
            int LS = ls,RS = rs;
            std::vector<int> ans(n + 1);
            cout << "Yes\n";
            int other = ls > 0 ? a[siz[ls]] : 0;
            // cerr << "!!! " << ls << " " << rs << "\n"; 
            while(ls > 0){
                vis[ls] = 1;
                ls = dp_from[ls][0];
            }
            auto dfs1 = [&](auto self,int x,int fa,int col) -> void {
                
                for(auto v:c[x]){
                    // cerr << v << " " << col << "\n";
                    ans[v] = col;
                }

                for(auto v:g[x]){
                    if(v == fa)continue;
                    if(vis[v])self(self,v,x,a[siz[v] - 1]);
                    else self(self,v,x,col);

                }
            };
            if(LS > 0)dfs1(dfs1,LS,f[LS],a[siz[LS] - 1]);
            while(rs > 0){
                vis[rs] = 1;
                rs = dp_from[rs][1];
            }
            auto dfs2 = [&](auto self,int x,int fa,int col) -> void {
                
                for(auto v:c[x]){
                    // cerr <<bel[x] << " " << v << " " << col << "\n";
                    ans[v] = col;
                }

                for(auto v:g[x]){
                    if(v == fa)continue;
                    if(vis[v])self(self,v,x,b[siz[v] - 1]);
                    else self(self,v,x,col);

                }
            };
            // cerr << RS << "\n";
            if(RS > 0)dfs2(dfs2,RS,f[RS],b[siz[RS] - 1]);
            for(int i = 1;i <= n;i ++)if(!ans[i]) ans[i] = other;
            for(int i = 1;i <= n;i ++)cout << ans[i] << " \n"[i == n];

            // std::vector<int> pd(m + 1);
            // int Ans = 0;
            // for(int i = 1;i <= n;i ++){
            //     for(auto [v,_]:e[i]){
            //         if(pd[_])continue;
            //         pd[_] = 1;
            //         Ans += abs(ans[v] - ans[i]);
            //     }
            // }
            // if(Ans == a.back() - a[0]){
            //     cerr << "AC\n";
            // }else {
            //     // return -1;
            //     cerr << "WA\n";
            // }

        }else {
            cout << "No\n";
        }
    }
}
Source code, Language: C++17

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 2 2 3
5 6
1 2
1 2
2 3
3 4
4 5
3 5
1 2 1 2 1
2 2
1 2
1 2
1 2

output:

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

result:

ok ok (5 test cases)

Test #2:

score: 0
Accepted
time: 207ms
memory: 12984kb

input:

100000
4 3
4 2
1 3
2 1
2 1 3 2
5 7
2 5
5 3
2 3
5 1
4 3
2 4
4 3
1 3 1 1 2
3 2
2 1
2 3
1 1 1
4 7
3 4
1 4
2 3
4 3
4 2
3 1
4 3
2 3 3 2
4 6
2 4
3 1
1 2
1 2
2 3
4 2
1 1 3 3
4 7
3 2
4 2
1 2
3 4
3 2
2 4
3 4
2 1 1 1
5 5
3 2
1 5
4 5
4 3
2 1
1 2 2 3 2
3 5
2 3
1 3
3 1
3 1
2 1
3 2 3
2 3
2 1
2 1
1 2
1 1
2 3
2 1
1...

output:

Yes
2 2 1 3
No
Yes
1 1 1
No
No
Yes
2 1 1 1
No
No
Yes
1 1
Yes
1 1
Yes
1 1
Yes
1 1 1 1
No
Yes
1 1 1 1 1
Yes
1 3 1 1 1
Yes
1 1 1
Yes
2 1
Yes
1 1 1 1 1
Yes
2 1
No
Yes
1 1
Yes
1 1 1
Yes
1 1
Yes
1 1 1 1
Yes
1 1
Yes
2 2 2 2 2
Yes
1 1 1 1 1
Yes
1 1
Yes
1 2 1 1
No
Yes
1 1
No
Yes
1 1
No
No
No
Yes
1 1 2 1 1
Ye...

result:

ok ok (100000 test cases)

Test #3:

score: 0
Accepted
time: 197ms
memory: 12988kb

input:

83335
9 17
1 4
8 9
5 2
1 3
2 7
1 7
2 8
6 7
2 4
1 8
5 8
7 1
8 6
4 6
4 7
6 9
7 9
7 3 4 4 7 4 2 4 8
6 9
3 1
1 2
3 5
1 2
3 4
4 5
6 3
6 1
6 2
4 3 2 2 1 3
9 8
9 3
5 7
5 9
2 6
1 8
4 1
4 2
4 3
4 2 5 3 4 5 4 5 4
6 7
2 1
1 5
6 1
3 1
6 5
2 4
5 3
2 1 2 1 2 1
4 6
2 1
4 2
1 4
1 2
1 4
3 1
2 2 4 2
6 10
2 3
3 5
2 1
...

output:

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

result:

ok ok (83335 test cases)

Test #4:

score: 0
Accepted
time: 174ms
memory: 12988kb

input:

58877
11 15
10 8
4 5
8 4
9 1
3 6
5 2
4 11
3 6
11 5
5 2
9 6
1 5
5 7
5 9
8 4
1 1 1 1 1 1 1 1 1 1 1
6 11
3 4
6 1
1 3
6 1
2 6
1 2
6 2
2 1
3 6
4 5
1 3
2 4 3 2 4 4
12 21
3 10
9 10
4 6
12 10
7 8
5 9
11 9
5 8
4 6
4 9
8 2
10 3
3 4
7 6
1 2
1 8
6 12
8 5
3 1
6 4
12 8
5 2 1 4 3 5 3 1 4 6 5 1
10 9
10 7
3 2
1 4
7 ...

output:

Yes
1 1 1 1 1 1 1 1 1 1 1
No
No
No
No
Yes
1 1
No
No
No
Yes
1 1 1 1
No
No
No
No
No
No
Yes
1 1 1 1 1
No
Yes
1 1 1 1
No
No
Yes
1 1 1 2 2
No
No
No
No
Yes
1 1 1 1 1 1 1 1 1 1 1 1 1
No
No
Yes
1 1 1
No
No
No
No
Yes
1 1
No
Yes
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
No
No
No
No
No
No
No
No
No
No
Yes
1 1
No
No
No
No
N...

result:

ok ok (58877 test cases)

Test #5:

score: 0
Accepted
time: 206ms
memory: 12968kb

input:

50000
10 9
4 3
4 2
5 1
4 5
7 8
5 7
9 10
9 6
8 10
4 1 4 4 1 3 2 1 3 2
10 9
7 4
3 5
9 6
2 9
2 10
3 2
3 8
3 1
7 9
1 1 2 2 2 2 2 2 2 2
10 9
7 3
8 4
8 6
8 7
9 10
2 5
2 1
2 9
7 5
2 1 1 1 2 2 2 2 1 1
10 9
4 2
2 6
3 10
1 3
8 7
1 8
6 3
5 9
7 5
4 4 2 3 3 1 3 3 1 3
10 9
7 3
1 9
7 1
6 5
1 5
2 8
6 8
10 4
2 4
2 4...

output:

Yes
2 1 1 1 2 4 3 3 4 4
Yes
2 2 2 1 2 2 1 2 2 2
Yes
2 2 1 1 2 1 1 1 2 2
Yes
3 4 3 4 1 3 2 3 1 3
Yes
1 3 1 4 2 2 1 3 1 4
Yes
3 4 3 1 2 2 3 4 3 4
Yes
1 2 2 2 3 3 1 2 1 4
Yes
1 3 3 1 1 3 2 3 4 4
Yes
2 3 2 3 1 2 1 2 4 4
Yes
2 3 3 2 2 3 1 2 4 1
Yes
2 3 3 3 2 1 1 2 1 2
Yes
1 1 2 1 3 1 1 3 2 3
Yes
3 1 2 3 ...

result:

ok ok (50000 test cases)

Test #6:

score: 0
Accepted
time: 168ms
memory: 13028kb

input:

5000
100 99
98 18
13 98
12 13
76 12
76 68
74 80
74 58
76 80
38 21
69 38
46 69
50 67
46 50
46 78
80 67
90 93
88 99
90 60
90 88
21 90
53 96
53 87
99 96
11 42
81 85
81 11
87 85
37 3
17 37
17 26
11 3
95 8
95 15
95 59
3 15
32 24
62 40
7 62
7 32
59 7
51 25
51 56
100 51
41 100
41 86
62 25
14 84
14 16
100 1...

output:

Yes
16 16 7 20 15 15 9 8 19 16 6 1 1 11 8 11 7 1 16 16 3 20 17 9 10 7 16 20 14 13 14 9 18 20 17 16 7 3 15 9 10 6 19 14 14 3 14 19 16 3 10 14 5 20 13 10 15 2 8 4 17 9 16 20 18 20 3 1 3 15 20 17 14 2 15 1 17 3 20 2 6 17 16 11 6 10 5 4 20 4 19 13 4 20 8 5 20 1 4 10
Yes
4 2 1 5 2 1 2 10 4 6 7 5 10 8 7 5...

result:

ok ok (5000 test cases)

Test #7:

score: 0
Accepted
time: 180ms
memory: 13496kb

input:

500
1000 999
532 116
445 532
834 445
540 432
144 540
427 834
427 144
564 261
564 427
948 692
119 111
119 429
965 316
714 975
787 714
537 787
793 537
793 119
948 793
948 965
564 692
603 575
17 603
22 759
390 22
73 390
73 17
965 759
491 790
897 491
703 69
359 703
217 359
776 557
897 776
258 897
31 258...

output:

Yes
63 18 31 27 38 42 31 9 35 15 32 23 18 85 68 9 3 49 40 16 66 3 14 16 62 76 25 19 17 55 4 19 73 89 89 43 74 8 22 59 9 51 13 9 16 84 44 47 72 33 65 90 49 48 22 63 45 89 69 73 19 68 18 20 6 37 37 61 4 77 53 24 3 81 57 36 15 45 50 82 76 21 9 50 69 47 61 13 27 23 75 26 91 53 22 33 72 24 29 68 54 73 45...

result:

ok ok (500 test cases)

Test #8:

score: 0
Accepted
time: 214ms
memory: 15804kb

input:

50
10000 9999
1099 7770
5310 7861
9812 3314
1099 7799
392 5622
5651 107
3262 5651
9852 1099
9852 3216
392 8051
9128 392
1141 9128
3252 9812
8671 116
2438 8671
3252 2438
5310 3252
9852 5310
7830 9852
6225 7830
213 6225
3908 213
2062 3908
4787 2062
7726 4787
6412 7726
1141 6412
1141 3262
7933 1672
355...

output:

Yes
94 95 231 265 327 297 260 44 110 330 341 225 76 418 275 132 80 416 158 300 106 248 407 174 237 166 288 189 91 200 61 127 271 153 218 198 61 353 303 3 305 306 315 201 189 11 12 385 231 196 366 380 73 418 119 64 288 163 396 325 399 185 26 263 252 46 306 240 137 372 103 411 415 112 256 254 247 332 ...

result:

ok ok (50 test cases)

Test #9:

score: 0
Accepted
time: 345ms
memory: 36904kb

input:

5
100000 99999
22355 12278
45499 67169
41047 76472
29154 41047
79175 29756
13716 48445
97977 83078
76471 63792
40743 9183
56989 43002
45499 27278
7876 13808
94004 15967
99866 56989
40743 99866
80181 40743
12918 8224
74066 29378
20226 6878
7876 20226
55266 23568
22646 2272
13688 45499
39216 14695
740...

output:

Yes
1881 1113 1607 646 1074 387 427 1903 1052 125 90 670 891 793 260 1181 1461 217 291 278 291 318 1279 1214 990 552 268 1738 1440 14 996 967 1489 1890 49 1898 231 1863 493 1550 679 1672 768 996 309 287 1787 1873 174 794 271 1538 637 708 396 539 73 1525 100 1825 904 1319 1939 1100 1427 148 1405 1898...

result:

ok ok (5 test cases)

Test #10:

score: 0
Accepted
time: 171ms
memory: 13260kb

input:

50000
10 18
4 3
4 2
5 1
4 5
7 8
5 7
9 10
9 6
8 10
4 2
2 4
9 10
8 7
1 5
4 3
1 5
6 10
5 1
4 1 4 4 1 3 2 1 3 2
10 14
10 5
7 10
9 7
4 9
6 4
1 6
2 3
8 2
7 2
1 9
5 7
5 7
9 5
8 10
1 1 2 2 1 1 1 2 1 1
10 18
3 8
2 3
1 7
2 1
9 5
4 9
10 4
10 6
3 4
6 4
2 1
9 6
10 5
4 10
1 8
4 6
4 9
8 5
2 2 1 2 2 1 2 1 1 1
10 20...

output:

Yes
2 1 1 1 2 4 3 3 4 4
No
No
Yes
2 2 2 1 2 2 2 2 2 2
No
Yes
1 2 1 2 2 1 1 1 2 2
Yes
3 4 2 3 1 4 4 1 2 3
Yes
2 3 3 1 2 4 2 2 3 4
Yes
3 2 1 2 1 2 3 1 1 1
Yes
1 2 1 1 1 2 1 2 1 1
Yes
2 3 1 3 1 2 1 4 2 2
Yes
2 1 2 1 2 2 1 1 2 1
Yes
4 4 2 3 3 2 2 1 3 2
No
Yes
2 3 2 3 3 3 1 3 3 2
Yes
3 1 2 2 1 1 1 2 1 2
...

result:

ok ok (50000 test cases)

Test #11:

score: 0
Accepted
time: 165ms
memory: 13124kb

input:

5000
100 182
98 18
13 98
12 13
76 12
76 68
74 80
74 58
76 80
38 21
69 38
46 69
50 67
46 50
46 78
80 67
90 93
88 99
90 60
90 88
21 90
53 96
53 87
99 96
11 42
81 85
81 11
87 85
37 3
17 37
17 26
11 3
95 8
95 15
95 59
3 15
32 24
62 40
7 62
7 32
59 7
51 25
51 56
100 51
41 100
41 86
62 25
14 84
14 16
100 ...

output:

Yes
16 16 7 20 15 15 9 8 19 16 6 1 1 11 8 11 7 1 16 16 3 20 17 9 10 7 16 20 14 13 14 9 18 20 17 16 7 3 15 9 10 6 19 14 14 3 14 19 16 3 10 14 5 20 13 10 15 2 8 4 17 9 16 20 18 20 3 1 3 15 20 17 14 2 15 1 17 3 20 2 6 17 16 11 6 10 5 4 20 4 19 13 4 20 8 5 20 1 4 10
Yes
1 9 14 7 11 4 9 12 9 8 5 9 13 9 1...

result:

ok ok (5000 test cases)

Test #12:

score: 0
Accepted
time: 160ms
memory: 13740kb

input:

500
1000 1815
532 116
445 532
834 445
540 432
144 540
427 834
427 144
564 261
564 427
948 692
119 111
119 429
965 316
714 975
787 714
537 787
793 537
793 119
948 793
948 965
564 692
603 575
17 603
22 759
390 22
73 390
73 17
965 759
491 790
897 491
703 69
359 703
217 359
776 557
897 776
258 897
31 25...

output:

Yes
63 18 31 27 38 42 31 9 35 15 32 23 18 85 68 9 3 49 40 16 66 3 14 16 62 76 25 19 17 55 4 19 73 89 89 43 74 8 22 59 9 51 13 9 16 84 44 47 72 33 65 90 49 48 22 63 45 89 69 73 19 68 18 20 6 37 37 61 4 77 53 24 3 81 57 36 15 45 50 82 76 21 9 50 69 47 61 13 27 23 75 26 91 53 22 33 72 24 29 68 54 73 45...

result:

ok ok (500 test cases)

Test #13:

score: 0
Accepted
time: 178ms
memory: 16500kb

input:

50
10000 18147
1099 7770
5310 7861
9812 3314
1099 7799
392 5622
5651 107
3262 5651
9852 1099
9852 3216
392 8051
9128 392
1141 9128
3252 9812
8671 116
2438 8671
3252 2438
5310 3252
9852 5310
7830 9852
6225 7830
213 6225
3908 213
2062 3908
4787 2062
7726 4787
6412 7726
1141 6412
1141 3262
7933 1672
35...

output:

Yes
94 95 231 265 327 297 260 44 110 330 341 225 76 418 275 132 80 416 158 300 106 248 407 174 237 166 288 189 91 200 61 127 271 153 218 198 61 353 303 3 305 306 315 201 189 11 12 385 231 196 366 380 73 418 119 64 288 163 396 325 399 185 26 263 252 46 306 240 137 372 103 411 415 112 256 254 247 332 ...

result:

ok ok (50 test cases)

Test #14:

score: 0
Accepted
time: 368ms
memory: 36112kb

input:

5
100000 181474
22355 12278
45499 67169
41047 76472
29154 41047
79175 29756
13716 48445
97977 83078
76471 63792
40743 9183
56989 43002
45499 27278
7876 13808
94004 15967
99866 56989
40743 99866
80181 40743
12918 8224
74066 29378
20226 6878
7876 20226
55266 23568
22646 2272
13688 45499
39216 14695
74...

output:

Yes
1881 1113 1607 646 1074 387 427 1903 1052 125 90 670 891 793 260 1181 1461 217 291 278 291 318 1279 1214 990 552 268 1738 1440 14 996 967 1489 1890 49 1898 231 1863 493 1550 679 1672 768 996 309 287 1787 1873 174 794 271 1538 637 708 396 539 73 1525 100 1825 904 1319 1939 1100 1427 148 1405 1898...

result:

ok ok (5 test cases)

Test #15:

score: 0
Accepted
time: 194ms
memory: 13048kb

input:

50000
10 20
4 3
4 2
5 1
4 5
7 8
5 7
9 10
9 6
8 10
4 2
2 4
9 10
8 7
1 5
4 3
1 5
6 10
5 1
3 2
1 5
4 1 4 4 1 3 2 1 3 2
10 20
3 6
9 10
4 3
4 9
5 8
5 2
7 1
7 5
10 7
1 7
7 1
7 1
3 6
1 5
1 7
4 10
4 10
8 2
10 4
5 1
1 2 1 1 1 2 2 2 2 1
10 20
7 4
3 7
6 2
4 6
9 10
9 8
5 9
5 1
6 5
5 1
10 9
8 10
5 1
7 3
8 10
1 5...

output:

Yes
2 1 1 1 2 4 3 3 4 4
Yes
2 2 1 1 2 1 2 2 1 1
Yes
3 4 4 4 3 4 4 2 2 2
Yes
3 1 1 2 3 2 2 2 1 3
Yes
2 3 2 3 1 2 1 2 4 4
Yes
1 2 2 2 1 4 4 1 1 4
Yes
3 1 2 4 4 1 2 2 2 3
Yes
1 2 1 2 1 1 1 1 2 2
Yes
2 2 1 1 1 2 2 3 1 2
Yes
2 3 1 2 2 3 2 3 1 1
Yes
1 1 3 3 1 1 2 2 1 2
Yes
1 3 1 2 2 2 2 1 2 3
Yes
3 2 1 1 ...

result:

ok ok (50000 test cases)

Test #16:

score: 0
Accepted
time: 150ms
memory: 13028kb

input:

5000
100 200
98 18
13 98
12 13
76 12
76 68
74 80
74 58
76 80
38 21
69 38
46 69
50 67
46 50
46 78
80 67
90 93
88 99
90 60
90 88
21 90
53 96
53 87
99 96
11 42
81 85
81 11
87 85
37 3
17 37
17 26
11 3
95 8
95 15
95 59
3 15
32 24
62 40
7 62
7 32
59 7
51 25
51 56
100 51
41 100
41 86
62 25
14 84
14 16
100 ...

output:

Yes
16 16 7 20 15 15 9 8 19 16 6 1 1 11 8 11 7 1 16 16 3 20 17 9 10 7 16 20 14 13 14 9 18 20 17 16 7 3 15 9 10 6 19 14 14 3 14 19 16 3 10 14 5 20 13 10 15 2 8 4 17 9 16 20 18 20 3 1 3 15 20 17 14 2 15 1 17 3 20 2 6 17 16 11 6 10 5 4 20 4 19 13 4 20 8 5 20 1 4 10
Yes
3 3 6 2 6 2 4 4 1 7 5 1 2 6 1 3 5...

result:

ok ok (5000 test cases)

Test #17:

score: 0
Accepted
time: 182ms
memory: 13680kb

input:

500
1000 2000
532 116
445 532
834 445
540 432
144 540
427 834
427 144
564 261
564 427
948 692
119 111
119 429
965 316
714 975
787 714
537 787
793 537
793 119
948 793
948 965
564 692
603 575
17 603
22 759
390 22
73 390
73 17
965 759
491 790
897 491
703 69
359 703
217 359
776 557
897 776
258 897
31 25...

output:

Yes
63 18 31 27 38 42 31 9 35 15 32 23 18 85 68 9 3 49 40 16 66 3 14 16 62 76 25 19 17 55 4 19 73 89 89 43 74 8 22 59 9 51 13 9 16 84 44 47 72 33 65 90 49 48 22 63 45 89 69 73 19 68 18 20 6 37 37 61 4 77 53 24 3 81 57 36 15 45 50 82 76 21 9 50 69 47 61 13 27 23 75 26 91 53 22 33 72 24 29 68 54 73 45...

result:

ok ok (500 test cases)

Test #18:

score: 0
Accepted
time: 230ms
memory: 15556kb

input:

50
10000 20000
1099 7770
5310 7861
9812 3314
1099 7799
392 5622
5651 107
3262 5651
9852 1099
9852 3216
392 8051
9128 392
1141 9128
3252 9812
8671 116
2438 8671
3252 2438
5310 3252
9852 5310
7830 9852
6225 7830
213 6225
3908 213
2062 3908
4787 2062
7726 4787
6412 7726
1141 6412
1141 3262
7933 1672
35...

output:

Yes
94 95 231 265 327 297 260 44 110 330 341 225 76 418 275 132 80 416 158 300 106 248 407 174 237 166 288 189 91 200 61 127 271 153 218 198 61 353 303 3 305 306 315 201 189 11 12 385 231 196 366 380 73 418 119 64 288 163 396 325 399 185 26 263 252 46 306 240 137 372 103 411 415 112 256 254 247 332 ...

result:

ok ok (50 test cases)

Test #19:

score: 0
Accepted
time: 388ms
memory: 34540kb

input:

5
100000 200000
22355 12278
45499 67169
41047 76472
29154 41047
79175 29756
13716 48445
97977 83078
76471 63792
40743 9183
56989 43002
45499 27278
7876 13808
94004 15967
99866 56989
40743 99866
80181 40743
12918 8224
74066 29378
20226 6878
7876 20226
55266 23568
22646 2272
13688 45499
39216 14695
74...

output:

Yes
1881 1113 1607 646 1074 387 427 1903 1052 125 90 670 891 793 260 1181 1461 217 291 278 291 318 1279 1214 990 552 268 1738 1440 14 996 967 1489 1890 49 1898 231 1863 493 1550 679 1672 768 996 309 287 1787 1873 174 794 271 1538 637 708 396 539 73 1525 100 1825 904 1319 1939 1100 1427 148 1405 1898...

result:

ok ok (5 test cases)

Test #20:

score: 0
Accepted
time: 175ms
memory: 13212kb

input:

100000
2 1
2 1
1 1
3 2
1 2
3 1
1 2 1
5 4
1 2
4 5
5 1
3 5
2 2 1 1 2
5 4
1 3
3 2
3 4
1 5
1 2 1 2 1
5 4
5 4
2 1
2 5
5 3
1 2 2 1 1
5 4
4 1
3 5
2 3
2 1
2 1 2 1 2
3 2
1 2
3 2
2 1 2
3 2
3 1
3 2
2 2 1
2 1
2 1
1 2
5 4
2 4
4 1
2 3
4 5
2 1 1 1 1
3 2
1 2
2 3
2 1 1
2 1
2 1
1 1
2 1
2 1
1 1
4 3
4 2
4 3
1 4
2 1 1 2...

output:

Yes
1 1
Yes
1 1 2
Yes
1 1 2 2 2
Yes
2 1 1 1 2
Yes
2 2 1 1 1
Yes
1 2 2 1 2
Yes
2 2 1
Yes
2 1 2
Yes
2 1
Yes
1 1 1 1 2
Yes
2 1 1
Yes
1 1
Yes
1 1
No
Yes
2 1 1
Yes
2 1 1
Yes
2 1 1
Yes
1 1
Yes
2 1 1
Yes
2 2 2 1 1
Yes
1 2 2 1
Yes
2 1
Yes
2 1 1 2
Yes
2 2 1
Yes
2 1 1
Yes
2 1
Yes
2 1 1 1 2
Yes
2 1
Yes
1 1
Yes...

result:

ok ok (100000 test cases)

Test #21:

score: 0
Accepted
time: 272ms
memory: 13048kb

input:

83461
4 3
3 2
1 3
3 4
1 2 2 2
2 1
2 1
1 2
6 5
5 6
3 1
5 2
3 6
6 4
1 2 2 1 1 2
7 6
3 4
1 3
7 4
6 2
2 4
3 5
1 1 1 1 1 2 1
9 8
2 1
6 8
9 4
5 9
3 5
6 9
2 9
4 7
2 2 2 1 2 1 2 2 1
8 7
1 6
7 3
2 6
3 4
5 8
5 1
3 5
2 1 1 2 1 2 2 2
2 1
2 1
1 2
2 1
2 1
1 2
2 1
1 2
1 1
8 7
7 3
2 5
7 8
5 8
5 4
6 1
6 2
1 1 1 2 1 ...

output:

Yes
2 1 2 2
Yes
2 1
No
Yes
1 1 1 1 1 2 1
No
Yes
1 1 2 2 2 1 2 2
Yes
2 1
Yes
2 1
Yes
1 1
Yes
2 1 1 1 1 2 1 1
Yes
1 2 2 2 1
Yes
1 1 1 2 1 1 2 1 1 1
Yes
2 1 1 2 2 1 2 1 1 1
Yes
1 1 1 1 1 2 1 2 1 1
Yes
1 2 1 2 2 2 1 1 1 1
Yes
1 1 2 1 2 2
Yes
1 1 2 1 2 2 2 2
Yes
2 1 1 2 2 1 1
Yes
1 1 2 2 2 2 1 2
Yes
2 1 ...

result:

ok ok (83461 test cases)

Test #22:

score: 0
Accepted
time: 142ms
memory: 13076kb

input:

9844
37 36
24 30
13 6
3 22
28 15
6 32
37 22
12 33
23 19
18 32
16 13
12 27
5 1
22 23
31 2
37 18
26 24
22 20
9 2
11 35
35 25
16 8
29 32
21 33
10 13
27 31
25 18
17 27
20 14
21 29
31 7
26 1
26 19
12 15
34 3
4 27
36 7
1 1 1 1 2 2 1 2 1 2 1 1 2 1 1 1 2 2 2 2 2 1 2 2 2 2 1 2 1 1 2 1 1 1 2 2 2
52 51
17 38
3...

output:

No
Yes
1 2 1 1 1 2 2 2 2 2 1 2 1 1 1 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 1 2 1 2 1 2
No
No
Yes
1 2 1 2 2 2 1 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 1 2 2 2 1 2 1 2 2 1 1 1 1 1 2 1 2 1 1 1 2 1 1 2 2 1 1 1 1 1 1 2 2 2 2 1 2 2 2 1 1 1 1 1 1 2 2 2 2 2 1 2 2 2 1 2 1 2 2 1 1 1 2 2 1...

result:

ok ok (9844 test cases)

Test #23:

score: 0
Accepted
time: 143ms
memory: 13504kb

input:

1018
608 607
48 591
364 115
340 236
175 115
506 470
511 105
242 136
119 70
464 246
505 286
114 405
453 514
330 250
337 96
157 563
421 189
51 217
503 336
604 573
341 297
281 241
402 250
446 22
100 447
301 261
58 342
520 310
40 96
224 477
104 430
210 536
434 387
340 137
145 456
558 539
355 214
322 524...

output:

No
No
No
No
No
No
Yes
2 2 1 2 1 2 1 1 1 1 1 1 2 1 2 2 2 1 2 1 1 2 2 2 1 1 2 1 1 2 1 1 1 2 2 1 1 1 1 1 1 2 1 2 2 1 1 2 1 1 2 2 2 2 2 1 2 2 1 1 2 1 2 1 2 2 1 1 1 2 2 1 2 2 2 2 2 2 2 1 2 2 1 2 2 2 1 1 2 1 2 1 1 2 2 1 2 2 2 2 2 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 2 2 2 1 2 1 2 1 2 1 1 1 1 1 2 2 2 2 2 ...

result:

ok ok (1018 test cases)

Test #24:

score: 0
Accepted
time: 172ms
memory: 15240kb

input:

87
5513 5512
1067 4346
3664 1879
771 4934
2611 3655
4151 663
1723 5228
4932 1932
2935 3224
3491 4583
3524 5446
4245 2617
371 4714
4068 1582
2649 642
2409 572
1963 792
1840 2762
2858 3580
2796 2653
1156 2745
967 3252
2410 1145
907 1061
4411 4465
5164 4754
3730 233
3306 4332
5337 2593
1369 4185
4755 2...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
2 2 1 2 1
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
2 1 2 2 1 2 2 1 1 2 2 2 1 1 1 2 2 2 2 1 2 1 2 2 2 1 2 1 1 2 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 2 2...

result:

ok ok (87 test cases)

Test #25:

score: 0
Accepted
time: 125ms
memory: 13100kb

input:

5000
100 99
42 90
90 80
15 90
81 90
43 94
90 6
90 70
90 9
90 61
22 90
90 36
90 83
90 18
53 90
90 16
90 55
90 100
2 90
65 90
90 10
12 90
90 77
90 98
92 90
58 50
24 90
90 8
43 31
90 74
14 90
90 75
33 90
28 90
71 90
78 90
90 13
11 35
95 90
11 29
39 90
90 76
82 90
56 90
90 52
90 91
85 31
47 90
50 35
20 ...

output:

No
Yes
56 56 56 56 56 56 3 93 56 56 56 56 56 56 56 56 56 56 56 56 56 3 93 3 56 56 3 56 56 56 56 56 56 3 56 56 56 56 56 56 56 56 56 3 56 56 3 3 56 56 56 56 56 56 56 56 56 56 56 56 56 56 93 93 56 56 56 56 56 3 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 3 56 56 93 56 56 56 56
No
...

result:

ok ok (5000 test cases)

Test #26:

score: 0
Accepted
time: 120ms
memory: 16088kb

input:

500
1000 999
758 157
157 380
560 157
512 157
584 157
157 784
896 157
139 157
768 157
849 157
895 157
157 369
782 157
263 157
157 785
607 157
773 157
813 157
157 172
135 157
157 970
157 772
328 157
157 92
461 157
641 157
157 250
157 376
157 355
157 876
157 845
667 157
556 157
157 412
157 490
884 157
...

output:

No
Yes
607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 911 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 6...

result:

ok ok (500 test cases)

Test #27:

score: 0
Accepted
time: 136ms
memory: 21168kb

input:

50
10000 9999
9684 8718
9684 5169
9595 9684
9684 6820
9476 9684
9684 968
1131 9684
5774 9684
8644 9684
9684 1878
9361 9684
9684 2733
2270 9684
6268 9684
9684 1129
9684 771
2827 9684
9684 1510
8937 9684
2055 9684
9684 9564
9684 41
9684 476
9684 6727
2441 9684
9684 8390
9684 1176
5715 9684
4194 9684
9...

output:

Yes
1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 8141 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1464 1...

result:

ok ok (50 test cases)

Test #28:

score: 0
Accepted
time: 258ms
memory: 37968kb

input:

5
100000 99999
20424 54074
54074 826
29805 54074
54074 64403
72518 54074
54074 68167
92728 54074
54074 86229
81267 54074
54074 62831
13080 54074
52946 54074
54074 18247
54074 1903
73633 54074
54074 36210
3991 54074
54074 22828
42978 54074
96146 54074
54074 27955
54074 75840
24035 54074
54074 83445
5...

output:

No
Yes
16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408 16408...

result:

ok ok (5 test cases)

Test #29:

score: 0
Accepted
time: 208ms
memory: 13040kb

input:

100000
5 4
5 1
2 3
5 3
2 4
1 5 4 2 3
5 4
2 5
1 3
1 5
4 3
1 5 4 3 1
5 4
1 4
4 3
5 1
2 3
5 1 1 3 1
5 4
2 3
5 4
1 5
1 2
3 4 2 5 3
5 4
1 4
2 4
5 3
5 2
5 4 5 4 2
5 4
3 2
1 3
4 2
1 5
4 1 3 1 1
5 4
2 1
2 5
3 5
4 3
2 2 1 5 5
5 4
2 1
4 2
3 4
1 5
4 5 4 5 5
5 4
3 4
2 5
1 2
1 4
2 3 4 2 3
5 4
3 1
3 2
1 4
5 2
2 1...

output:

Yes
5 2 3 1 4
Yes
3 5 1 1 4
Yes
3 1 1 1 5
Yes
3 4 5 2 3
Yes
5 4 2 5 4
Yes
3 1 1 1 4
Yes
5 5 2 1 2
Yes
5 5 4 4 5
Yes
3 2 4 3 2
Yes
3 1 2 5 1
Yes
4 4 1 4 4
Yes
5 5 3 1 1
Yes
5 4 2 1 4
Yes
4 3 5 5 3
Yes
3 5 2 4 2
Yes
5 2 3 3 2
Yes
1 4 1 3 5
Yes
5 1 1 1 3
Yes
5 2 1 3 1
Yes
5 3 2 2 1
Yes
5 5 5 2 2
Yes
5 ...

result:

ok ok (100000 test cases)

Test #30:

score: 0
Accepted
time: 189ms
memory: 13016kb

input:

50000
10 9
5 9
5 7
1 3
4 10
2 6
8 7
1 2
3 9
4 6
2 6 2 10 9 7 5 1 9 4
10 9
4 10
7 10
5 9
4 2
1 7
8 1
3 6
5 6
3 8
9 4 10 6 5 4 6 3 9 7
10 9
3 2
1 9
4 7
6 5
6 10
1 8
3 4
9 2
10 8
2 10 3 4 1 5 9 9 5 5
10 9
5 6
3 7
1 4
2 8
6 1
4 10
7 5
9 8
2 10
7 6 9 1 7 8 7 5 4 4
10 9
5 10
4 7
10 1
6 4
3 6
5 8
9 8
2 7
1...

output:

Yes
6 7 5 9 2 9 2 1 4 10
Yes
6 3 7 4 9 9 5 6 10 4
Yes
5 4 3 2 10 9 1 5 5 9
Yes
7 4 9 6 7 7 8 4 1 5
Yes
6 10 7 9 4 7 10 2 1 6
Yes
4 10 2 8 7 2 9 9 1 5
Yes
4 4 3 4 9 8 6 4 6 1
Yes
2 7 2 9 1 10 8 6 10 1
Yes
7 9 10 7 1 9 7 3 6 3
Yes
10 9 7 4 9 1 9 7 6 7
Yes
3 1 6 3 8 6 9 5 1 1
Yes
6 10 9 10 9 7 10 2 4 1...

result:

ok ok (50000 test cases)

Test #31:

score: 0
Accepted
time: 158ms
memory: 12968kb

input:

5000
100 99
79 67
26 83
7 10
90 97
16 18
49 62
70 30
44 47
70 52
68 48
9 18
21 96
19 6
99 62
31 40
96 43
50 46
60 36
32 5
95 38
3 34
86 64
59 42
88 12
27 19
75 40
10 21
25 81
24 91
15 78
6 81
66 3
55 2
69 66
42 87
14 95
99 2
73 79
39 56
76 78
80 77
24 36
74 32
28 48
90 94
13 89
35 63
1 4
100 64
20 5...

output:

Yes
93 83 33 91 42 65 100 66 52 100 94 36 23 22 55 54 72 53 65 58 99 2 77 50 66 3 63 97 90 75 19 42 7 32 39 49 62 21 57 19 72 69 98 30 60 62 31 96 84 61 97 77 15 58 82 57 70 60 69 44 7 84 40 29 42 33 10 95 34 75 91 74 7 40 19 56 11 55 9 13 65 15 4 42 88 28 66 35 24 55 51 25 72 54 22 98 55 93 84 30
Y...

result:

ok ok (5000 test cases)

Test #32:

score: 0
Accepted
time: 173ms
memory: 13360kb

input:

500
1000 999
683 508
513 98
140 785
613 8
128 691
43 37
979 180
270 227
648 203
124 446
876 124
558 23
666 934
472 703
808 24
999 64
239 64
544 284
91 190
328 741
675 498
548 29
594 634
106 554
287 231
872 891
802 136
898 646
395 164
324 426
562 272
837 182
425 797
691 779
736 443
405 288
176 321
74...

output:

Yes
253 985 772 782 333 467 7 942 113 284 624 440 827 511 735 271 963 113 670 533 203 611 552 896 745 44 694 681 326 85 228 931 15 98 815 5 602 998 691 492 250 485 600 617 247 413 445 831 99 557 909 415 164 794 944 440 128 683 681 534 471 200 18 122 772 432 242 366 270 657 840 18 416 562 625 775 404...

result:

ok ok (500 test cases)

Test #33:

score: 0
Accepted
time: 207ms
memory: 16592kb

input:

50
10000 9999
9637 8572
7031 5112
3079 1374
2344 778
4133 6047
1956 8298
9108 8664
6385 2668
6259 2037
2973 520
1994 3513
2073 5633
5048 7941
8585 563
9890 7835
4157 1320
6870 5096
8472 9439
5608 5845
2669 9670
9453 9764
7138 2800
1952 4136
8586 1600
151 3415
3168 2873
5874 2038
6037 1287
1922 9329
...

output:

Yes
3520 9167 5630 7898 5084 642 4182 9189 7361 4380 7582 2915 4728 9078 1506 5298 5932 6919 119 6155 7088 4671 2377 9561 9354 1216 8223 8452 9015 136 6873 9836 9021 6830 520 1804 6817 9539 3319 4247 5642 1794 1302 8663 5491 8126 6705 5918 9309 3321 7029 447 262 9450 2043 7043 9064 3791 5788 1627 60...

result:

ok ok (50 test cases)

Test #34:

score: 0
Accepted
time: 385ms
memory: 50788kb

input:

5
100000 99999
43561 63383
6723 36002
56906 49405
87795 27838
17049 80864
12016 19662
63514 14364
12523 36574
87618 10650
41589 64362
56354 98915
24876 4283
83443 13573
45524 57667
62580 39064
88873 34690
7098 9024
50768 81026
48266 16280
68435 22863
28186 74660
49511 28449
35015 30939
38574 10988
5...

output:

Yes
30208 25533 35841 75812 89385 55277 12581 68022 21357 86652 14824 3386 10972 84434 2078 49744 15165 67446 37850 94036 31128 22498 10480 37592 69900 31964 345 22090 72660 45102 4335 25363 76683 51015 97000 1182 63863 35678 1295 92418 76937 27710 43837 93084 26963 37902 53998 5833 40293 66354 8668...

result:

ok ok (5 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-11-30 07:51:06 | OpenSource Project