oj.uz

Submission #779445

# Submission time Handle Problem Language Result Execution time Memory
779445 2023-07-11T12:14:15 Z definitelynotmee Building Skyscrapers (CEOI19_skyscrapers) C++17
100 / 100
 1657 ms 117060 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
 
    int n;
    cin >> n;
    int t;
    cin >> t;
 
    vector<pii> v(n);
 
    for(auto & i : v)
        cin >> i.ff >> i.ss;
 
    map<pii,int> mp;
 
    for(int i = 0; i < n; i++){
        mp[{v[i].ff,v[i].ss}] = i;
    }
 
    vector<int> pai(n);
    iota(all(pai),0);
    int dx[]{1,0,-1,0}, dy[]{0,1,0,-1};
    int dx2[]{-1,-1,-1,0,1,1,1,0}, dy2[]{-1,0,1,1,1,0,-1,-1};
 
    auto find =[&](int id, auto f) -> int {
        if(pai[id] == id)
            return id;
        return pai[id] = f(pai[id],f);
    };
    int cmp = n;
    auto onion =[&](int a, int b) -> void {
        a = find(a,find);
        b = find(b,find);
        if(a != b){
            pai[a] = b;
            cmp--;
        }
 
    };
    vector<int> deg(n);
 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 8; j++){
            int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
            if(mp.count({xi,yi})){
                onion(i,mp[{xi,yi}]);
                deg[i]++;
                // cout << i << "++\n";
                // cout << mp[{xi,yi}] << "++\n";
            }
        }
    }
 
    if(cmp > 1){
        cout << "NO\n";
        return 0;
    }
 
 
    t = n;
    
    vector<array<int,8>> adj(v.size(),array<int,8>({}));


    for(int i = 0; i < n; i++){
        for(int j = 0; j < 8; j++){
            int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
            if(!mp.count({xi,yi})){
                mp[{xi,yi}] = t++;
                v.push_back({xi,yi});
            }
            adj[i][j] = mp[{xi,yi}];
        }
    }
    adj.resize(t,array<int,8>({}));

    pai = vector<int>(t);
    iota(all(pai),0);
 
    for(int i = n; i < t; i++){
        for(int j = 1; j < 8; j+=2){
            int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
            
            if(mp.count({xi,yi})){
                const int curval = mp[{xi,yi}];

                adj[i][j] = curval;
                
                if(curval >= n)
                    onion(i,adj[i][j]);
            } else adj[i][j] = -1;
        }
    }
 
 
 
 
    vector<int> check(n);
 
    priority_queue<int> pq;
 
    vector<int> passed(v.size());
    vector<int> reached(n);
    
    
    auto dfs =[&](int id, auto dfs) -> void {
        passed[id] = 1;
        for(int i = 1; i < 8; i+=2){
            int curval = adj[id][i];
            if(curval != -1 && !passed[curval]){
 
                if(curval >= n){
                    dfs(curval,dfs);
                } else {
                    if(!check[curval]){
                        check[curval] = 1;
                        reached[curval] = 1;
                        pq.push(curval);
                    }
                }
            }
        }
 
    };
 
    int mn = 0;
 
    for(int i = 1; i < n; i++){
        mn = min(mn,i,[&](int a, int b){
            return v[a].ff < v[b].ff;
        });
    }
    dfs(mp[{v[mn].ff-1,v[mn].ss}],dfs);
    
   
 
    vector<int> resp;
 
    while(!pq.empty()){
        int cur = pq.top();
 
        pq.pop();
        if(check[cur] == 2)
            continue;
 
        if(deg[cur]>=2){//check comp
            bool failed = 0;
 
            for(int i = 1; i < 4; i+=2){
                int k = i+1;
                int sum = 0;
                while(k != i+4){
                    int xi = v[cur].ff+dx2[k], yi = v[cur].ss+dy2[k];
                    sum+=adj[cur][k] < n && check[adj[cur][k]] < 2;
                    k++;
                }
 
                if(sum < deg[cur] && sum > 0 && find(adj[cur][i],find) == find(adj[cur][i+4],find)){
                    failed = 1;
                    break;
                }
            }
 
            for(int i = 1; i < 8; i+=2){ 
                if(find(adj[cur][i],find) == find(adj[cur][(i+2)%8],find) && adj[cur][(i+1)%8] < n && check[adj[cur][(i+1)%8]] < 2){
                    failed = 1;
                    break;
                }
            }
            if(failed){
                check[cur] = 0;
                continue;
            }
 
        }
 
        check[cur] = 2;
        resp.push_back(cur);
        //cout << "push " << cur << '\n';
        dfs(cur,dfs);
        for(int i = 0; i < 8; i++){
            const int curval = adj[cur][i];
            if(curval < n){
                deg[curval]--;
                if(!check[curval] && reached[curval])
                    pq.push(curval), check[curval] = 1;
            }
        }
        for(int i = 1; i < 8; i+=2){
            const int curval = adj[cur][i];
            if(curval >= n || check[curval] == 2){
                onion(cur,curval);
            }
        }
    }
    reverse(all(resp));
 
    if(resp.size() == n){
        cout << "YES\n";
        for(int i : resp)
            cout << i + 1 << '\n';
    } else cout << "NO\n";
 
 
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:164:25: warning: unused variable 'xi' [-Wunused-variable]
  164 |                     int xi = v[cur].ff+dx2[k], yi = v[cur].ss+dy2[k];
      |                         ^~
skyscrapers.cpp:164:48: warning: unused variable 'yi' [-Wunused-variable]
  164 |                     int xi = v[cur].ff+dx2[k], yi = v[cur].ss+dy2[k];
      |                                                ^~
skyscrapers.cpp:209:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  209 |     if(resp.size() == n){
      |        ~~~~~~~~~~~~^~~~
skyscrapers.cpp:33:9: warning: unused variable 'dx' [-Wunused-variable]
   33 |     int dx[]{1,0,-1,0}, dy[]{0,1,0,-1};
      |         ^~
skyscrapers.cpp:33:25: warning: unused variable 'dy' [-Wunused-variable]
   33 |     int dx[]{1,0,-1,0}, dy[]{0,1,0,-1};
      |                         ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ans=YES N=1
2 Correct 1 ms 212 KB ans=YES N=4
3 Correct 1 ms 212 KB ans=NO N=4
4 Correct 1 ms 212 KB ans=YES N=5
5 Correct 1 ms 212 KB ans=YES N=9
6 Correct 1 ms 212 KB ans=YES N=5
7 Correct 1 ms 324 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 1 ms 320 KB ans=YES N=10
12 Correct 1 ms 324 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 312 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ans=YES N=1
2 Correct 1 ms 212 KB ans=YES N=4
3 Correct 1 ms 212 KB ans=NO N=4
4 Correct 1 ms 212 KB ans=YES N=5
5 Correct 1 ms 212 KB ans=YES N=9
6 Correct 1 ms 212 KB ans=YES N=5
7 Correct 1 ms 324 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 1 ms 320 KB ans=YES N=10
12 Correct 1 ms 324 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 312 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 1 ms 340 KB ans=YES N=100
20 Correct 1 ms 340 KB ans=YES N=185
21 Correct 1 ms 212 KB ans=NO N=174
22 Correct 1 ms 320 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 340 KB ans=YES N=183
26 Correct 1 ms 340 KB ans=YES N=188
27 Correct 2 ms 340 KB ans=YES N=183
28 Correct 1 ms 340 KB ans=YES N=189
29 Correct 1 ms 320 KB ans=YES N=200
30 Correct 1 ms 340 KB ans=YES N=190
31 Correct 1 ms 340 KB ans=YES N=187
32 Correct 1 ms 340 KB ans=YES N=187
33 Correct 1 ms 340 KB ans=YES N=182
34 Correct 2 ms 340 KB ans=YES N=184
35 Correct 2 ms 340 KB ans=YES N=188
36 Correct 1 ms 340 KB ans=YES N=181
37 Correct 1 ms 340 KB ans=YES N=188
38 Correct 1 ms 452 KB ans=YES N=191
39 Correct 1 ms 340 KB ans=YES N=196
40 Correct 1 ms 340 KB ans=YES N=196
41 Correct 1 ms 340 KB ans=YES N=196
42 Correct 1 ms 340 KB ans=YES N=196
43 Correct 2 ms 340 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ans=YES N=1
2 Correct 1 ms 212 KB ans=YES N=4
3 Correct 1 ms 212 KB ans=NO N=4
4 Correct 1 ms 212 KB ans=YES N=5
5 Correct 1 ms 212 KB ans=YES N=9
6 Correct 1 ms 212 KB ans=YES N=5
7 Correct 1 ms 324 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 1 ms 320 KB ans=YES N=10
12 Correct 1 ms 324 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 312 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 1 ms 340 KB ans=YES N=100
20 Correct 1 ms 340 KB ans=YES N=185
21 Correct 1 ms 212 KB ans=NO N=174
22 Correct 1 ms 320 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 340 KB ans=YES N=183
26 Correct 1 ms 340 KB ans=YES N=188
27 Correct 2 ms 340 KB ans=YES N=183
28 Correct 1 ms 340 KB ans=YES N=189
29 Correct 1 ms 320 KB ans=YES N=200
30 Correct 1 ms 340 KB ans=YES N=190
31 Correct 1 ms 340 KB ans=YES N=187
32 Correct 1 ms 340 KB ans=YES N=187
33 Correct 1 ms 340 KB ans=YES N=182
34 Correct 2 ms 340 KB ans=YES N=184
35 Correct 2 ms 340 KB ans=YES N=188
36 Correct 1 ms 340 KB ans=YES N=181
37 Correct 1 ms 340 KB ans=YES N=188
38 Correct 1 ms 452 KB ans=YES N=191
39 Correct 1 ms 340 KB ans=YES N=196
40 Correct 1 ms 340 KB ans=YES N=196
41 Correct 1 ms 340 KB ans=YES N=196
42 Correct 1 ms 340 KB ans=YES N=196
43 Correct 2 ms 340 KB ans=YES N=195
44 Correct 3 ms 468 KB ans=NO N=1934
45 Correct 3 ms 468 KB ans=NO N=1965
46 Correct 6 ms 588 KB ans=YES N=1824
47 Correct 7 ms 596 KB ans=YES N=1981
48 Correct 6 ms 648 KB ans=YES N=1814
49 Correct 7 ms 724 KB ans=YES N=1854
50 Correct 7 ms 596 KB ans=YES N=1831
51 Correct 8 ms 724 KB ans=YES N=2000
52 Correct 9 ms 820 KB ans=YES N=1847
53 Correct 8 ms 780 KB ans=YES N=1819
54 Correct 7 ms 632 KB ans=YES N=1986
55 Correct 10 ms 980 KB ans=YES N=2000
56 Correct 11 ms 1236 KB ans=YES N=1834
57 Correct 13 ms 1108 KB ans=YES N=1860
58 Correct 13 ms 1204 KB ans=YES N=1898
59 Correct 11 ms 1108 KB ans=YES N=1832
60 Correct 12 ms 1744 KB ans=YES N=1929
61 Correct 9 ms 712 KB ans=YES N=1919
62 Correct 11 ms 1248 KB ans=YES N=1882
63 Correct 17 ms 1824 KB ans=YES N=1922
64 Correct 7 ms 848 KB ans=YES N=1989
65 Correct 10 ms 1100 KB ans=YES N=1978
66 Correct 10 ms 1236 KB ans=YES N=1867
67 Correct 9 ms 980 KB ans=YES N=1942

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB ans=NO N=1934
2 Correct 3 ms 464 KB ans=NO N=1965
3 Correct 7 ms 596 KB ans=YES N=1824
4 Correct 8 ms 596 KB ans=YES N=1981
5 Correct 6 ms 596 KB ans=YES N=1814
6 Correct 7 ms 704 KB ans=YES N=1854
7 Correct 6 ms 596 KB ans=YES N=1831
8 Correct 8 ms 744 KB ans=YES N=2000
9 Correct 7 ms 724 KB ans=YES N=1847
10 Correct 8 ms 876 KB ans=YES N=1819
11 Correct 7 ms 604 KB ans=YES N=1986
12 Correct 10 ms 980 KB ans=YES N=2000
13 Correct 10 ms 1236 KB ans=YES N=1834
14 Correct 10 ms 1236 KB ans=YES N=1860
15 Correct 10 ms 1232 KB ans=YES N=1898
16 Correct 9 ms 1108 KB ans=YES N=1832
17 Correct 12 ms 1912 KB ans=YES N=1929
18 Correct 8 ms 820 KB ans=YES N=1919
19 Correct 11 ms 1248 KB ans=YES N=1882
20 Correct 13 ms 1836 KB ans=YES N=1922
21 Correct 9 ms 948 KB ans=YES N=1989
22 Correct 8 ms 1104 KB ans=YES N=1978
23 Correct 8 ms 1236 KB ans=YES N=1867

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ans=YES N=1
2 Correct 1 ms 212 KB ans=YES N=4
3 Correct 1 ms 212 KB ans=NO N=4
4 Correct 1 ms 212 KB ans=YES N=5
5 Correct 1 ms 212 KB ans=YES N=9
6 Correct 1 ms 212 KB ans=YES N=5
7 Correct 1 ms 324 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 1 ms 212 KB ans=YES N=10
10 Correct 1 ms 212 KB ans=YES N=10
11 Correct 1 ms 320 KB ans=YES N=10
12 Correct 1 ms 324 KB ans=YES N=9
13 Correct 0 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 312 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 1 ms 340 KB ans=YES N=100
20 Correct 1 ms 340 KB ans=YES N=185
21 Correct 1 ms 212 KB ans=NO N=174
22 Correct 1 ms 320 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 340 KB ans=YES N=183
26 Correct 1 ms 340 KB ans=YES N=188
27 Correct 2 ms 340 KB ans=YES N=183
28 Correct 1 ms 340 KB ans=YES N=189
29 Correct 1 ms 320 KB ans=YES N=200
30 Correct 1 ms 340 KB ans=YES N=190
31 Correct 1 ms 340 KB ans=YES N=187
32 Correct 1 ms 340 KB ans=YES N=187
33 Correct 1 ms 340 KB ans=YES N=182
34 Correct 2 ms 340 KB ans=YES N=184
35 Correct 2 ms 340 KB ans=YES N=188
36 Correct 1 ms 340 KB ans=YES N=181
37 Correct 1 ms 340 KB ans=YES N=188
38 Correct 1 ms 452 KB ans=YES N=191
39 Correct 1 ms 340 KB ans=YES N=196
40 Correct 1 ms 340 KB ans=YES N=196
41 Correct 1 ms 340 KB ans=YES N=196
42 Correct 1 ms 340 KB ans=YES N=196
43 Correct 2 ms 340 KB ans=YES N=195
44 Correct 3 ms 468 KB ans=NO N=1934
45 Correct 3 ms 468 KB ans=NO N=1965
46 Correct 6 ms 588 KB ans=YES N=1824
47 Correct 7 ms 596 KB ans=YES N=1981
48 Correct 6 ms 648 KB ans=YES N=1814
49 Correct 7 ms 724 KB ans=YES N=1854
50 Correct 7 ms 596 KB ans=YES N=1831
51 Correct 8 ms 724 KB ans=YES N=2000
52 Correct 9 ms 820 KB ans=YES N=1847
53 Correct 8 ms 780 KB ans=YES N=1819
54 Correct 7 ms 632 KB ans=YES N=1986
55 Correct 10 ms 980 KB ans=YES N=2000
56 Correct 11 ms 1236 KB ans=YES N=1834
57 Correct 13 ms 1108 KB ans=YES N=1860
58 Correct 13 ms 1204 KB ans=YES N=1898
59 Correct 11 ms 1108 KB ans=YES N=1832
60 Correct 12 ms 1744 KB ans=YES N=1929
61 Correct 9 ms 712 KB ans=YES N=1919
62 Correct 11 ms 1248 KB ans=YES N=1882
63 Correct 17 ms 1824 KB ans=YES N=1922
64 Correct 7 ms 848 KB ans=YES N=1989
65 Correct 10 ms 1100 KB ans=YES N=1978
66 Correct 10 ms 1236 KB ans=YES N=1867
67 Correct 9 ms 980 KB ans=YES N=1942
68 Correct 141 ms 5996 KB ans=NO N=66151
69 Correct 102 ms 5884 KB ans=NO N=64333
70 Correct 329 ms 10960 KB ans=YES N=69316
71 Correct 324 ms 10568 KB ans=YES N=66695
72 Correct 331 ms 10940 KB ans=YES N=68436
73 Correct 340 ms 11156 KB ans=YES N=70000
74 Correct 323 ms 11252 KB ans=YES N=68501
75 Correct 341 ms 11708 KB ans=YES N=70000
76 Correct 341 ms 12312 KB ans=YES N=65009
77 Correct 454 ms 20360 KB ans=YES N=67007
78 Correct 487 ms 25388 KB ans=YES N=66357
79 Correct 508 ms 30204 KB ans=YES N=65430
80 Correct 500 ms 26932 KB ans=YES N=65790
81 Correct 493 ms 24696 KB ans=YES N=66020
82 Correct 451 ms 22016 KB ans=YES N=65809
83 Correct 359 ms 14896 KB ans=YES N=65651
84 Correct 658 ms 35140 KB ans=YES N=68040
85 Correct 578 ms 32864 KB ans=YES N=66570
86 Correct 322 ms 11420 KB ans=YES N=65421
87 Correct 347 ms 14148 KB ans=YES N=68351
88 Correct 302 ms 10528 KB ans=YES N=67027
89 Correct 351 ms 18676 KB ans=YES N=68879
90 Correct 331 ms 13468 KB ans=YES N=67256
91 Correct 872 ms 23876 KB ans=YES N=148315
92 Correct 233 ms 12656 KB ans=NO N=142745
93 Correct 185 ms 14688 KB ans=NO N=148443
94 Correct 849 ms 24396 KB ans=YES N=148328
95 Correct 855 ms 24576 KB ans=YES N=147855
96 Correct 882 ms 24704 KB ans=YES N=150000
97 Correct 811 ms 24040 KB ans=YES N=144725
98 Correct 890 ms 24784 KB ans=YES N=149445
99 Correct 816 ms 24224 KB ans=YES N=144455
100 Correct 803 ms 24180 KB ans=YES N=143487
101 Correct 865 ms 25108 KB ans=YES N=149688
102 Correct 1167 ms 46224 KB ans=YES N=141481
103 Correct 1521 ms 79216 KB ans=YES N=147430
104 Correct 962 ms 36280 KB ans=YES N=142247
105 Correct 1164 ms 43616 KB ans=YES N=149941
106 Correct 1362 ms 75832 KB ans=YES N=141635
107 Correct 1425 ms 58888 KB ans=YES N=142896
108 Correct 1529 ms 64704 KB ans=YES N=142069
109 Correct 876 ms 28752 KB ans=YES N=142378
110 Correct 1318 ms 69384 KB ans=YES N=150000
111 Correct 1657 ms 102020 KB ans=YES N=141452
112 Correct 1498 ms 110696 KB ans=YES N=134453
113 Correct 1307 ms 116872 KB ans=YES N=144172

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 5940 KB ans=NO N=66151
2 Correct 90 ms 5860 KB ans=NO N=64333
3 Correct 316 ms 11008 KB ans=YES N=69316
4 Correct 307 ms 10696 KB ans=YES N=66695
5 Correct 323 ms 10952 KB ans=YES N=68436
6 Correct 324 ms 11204 KB ans=YES N=70000
7 Correct 332 ms 11244 KB ans=YES N=68501
8 Correct 333 ms 11708 KB ans=YES N=70000
9 Correct 342 ms 12288 KB ans=YES N=65009
10 Correct 439 ms 20376 KB ans=YES N=67007
11 Correct 480 ms 25456 KB ans=YES N=66357
12 Correct 518 ms 30232 KB ans=YES N=65430
13 Correct 491 ms 26928 KB ans=YES N=65790
14 Correct 532 ms 24792 KB ans=YES N=66020
15 Correct 468 ms 21976 KB ans=YES N=65809
16 Correct 352 ms 14820 KB ans=YES N=65651
17 Correct 639 ms 35148 KB ans=YES N=68040
18 Correct 613 ms 32788 KB ans=YES N=66570
19 Correct 309 ms 11404 KB ans=YES N=65421
20 Correct 371 ms 14192 KB ans=YES N=68351
21 Correct 315 ms 10560 KB ans=YES N=67027
22 Correct 344 ms 18584 KB ans=YES N=68879
23 Correct 328 ms 13600 KB ans=YES N=67256

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB ans=NO N=1934
2 Correct 3 ms 464 KB ans=NO N=1965
3 Correct 7 ms 596 KB ans=YES N=1824
4 Correct 8 ms 596 KB ans=YES N=1981
5 Correct 6 ms 596 KB ans=YES N=1814
6 Correct 7 ms 704 KB ans=YES N=1854
7 Correct 6 ms 596 KB ans=YES N=1831
8 Correct 8 ms 744 KB ans=YES N=2000
9 Correct 7 ms 724 KB ans=YES N=1847
10 Correct 8 ms 876 KB ans=YES N=1819
11 Correct 7 ms 604 KB ans=YES N=1986
12 Correct 10 ms 980 KB ans=YES N=2000
13 Correct 10 ms 1236 KB ans=YES N=1834
14 Correct 10 ms 1236 KB ans=YES N=1860
15 Correct 10 ms 1232 KB ans=YES N=1898
16 Correct 9 ms 1108 KB ans=YES N=1832
17 Correct 12 ms 1912 KB ans=YES N=1929
18 Correct 8 ms 820 KB ans=YES N=1919
19 Correct 11 ms 1248 KB ans=YES N=1882
20 Correct 13 ms 1836 KB ans=YES N=1922
21 Correct 9 ms 948 KB ans=YES N=1989
22 Correct 8 ms 1104 KB ans=YES N=1978
23 Correct 8 ms 1236 KB ans=YES N=1867
24 Correct 140 ms 5940 KB ans=NO N=66151
25 Correct 90 ms 5860 KB ans=NO N=64333
26 Correct 316 ms 11008 KB ans=YES N=69316
27 Correct 307 ms 10696 KB ans=YES N=66695
28 Correct 323 ms 10952 KB ans=YES N=68436
29 Correct 324 ms 11204 KB ans=YES N=70000
30 Correct 332 ms 11244 KB ans=YES N=68501
31 Correct 333 ms 11708 KB ans=YES N=70000
32 Correct 342 ms 12288 KB ans=YES N=65009
33 Correct 439 ms 20376 KB ans=YES N=67007
34 Correct 480 ms 25456 KB ans=YES N=66357
35 Correct 518 ms 30232 KB ans=YES N=65430
36 Correct 491 ms 26928 KB ans=YES N=65790
37 Correct 532 ms 24792 KB ans=YES N=66020
38 Correct 468 ms 21976 KB ans=YES N=65809
39 Correct 352 ms 14820 KB ans=YES N=65651
40 Correct 639 ms 35148 KB ans=YES N=68040
41 Correct 613 ms 32788 KB ans=YES N=66570
42 Correct 309 ms 11404 KB ans=YES N=65421
43 Correct 371 ms 14192 KB ans=YES N=68351
44 Correct 315 ms 10560 KB ans=YES N=67027
45 Correct 344 ms 18584 KB ans=YES N=68879
46 Correct 328 ms 13600 KB ans=YES N=67256
47 Correct 848 ms 23840 KB ans=YES N=148315
48 Correct 233 ms 12620 KB ans=NO N=142745
49 Correct 184 ms 14476 KB ans=NO N=148443
50 Correct 797 ms 24504 KB ans=YES N=148328
51 Correct 796 ms 24448 KB ans=YES N=147855
52 Correct 808 ms 24616 KB ans=YES N=150000
53 Correct 796 ms 23796 KB ans=YES N=144725
54 Correct 803 ms 24592 KB ans=YES N=149445
55 Correct 810 ms 24136 KB ans=YES N=144455
56 Correct 777 ms 23848 KB ans=YES N=143487
57 Correct 857 ms 24972 KB ans=YES N=149688
58 Correct 1133 ms 46012 KB ans=YES N=141481
59 Correct 1419 ms 78964 KB ans=YES N=147430
60 Correct 925 ms 35992 KB ans=YES N=142247
61 Correct 1115 ms 43496 KB ans=YES N=149941
62 Correct 1301 ms 75580 KB ans=YES N=141635
63 Correct 1297 ms 58720 KB ans=YES N=142896
64 Correct 1426 ms 64684 KB ans=YES N=142069
65 Correct 820 ms 28676 KB ans=YES N=142378
66 Correct 1166 ms 69152 KB ans=YES N=150000
67 Correct 1585 ms 101788 KB ans=YES N=141452
68 Correct 1410 ms 110732 KB ans=YES N=134453
69 Correct 1228 ms 117060 KB ans=YES N=144172