oj.uz

Submission #343839

# Submission time Handle Problem Language Result Execution time Memory
343839 2021-01-04T14:30:17 Z koketsu Nice sequence (IZhO18_sequence) C++17
100 / 100
 1913 ms 45532 KB 
#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const LL Mxn = 1e6 + 7;
const LL Mod = 1e9 + 7;
const LL Inf = 1e14 + 7;

vector <int> Top;

int A[Mxn];

bool Used[Mxn];

void Dfs(int v, int Mid, int N, int M){
    Used[v] = true;
    if(v + N <= Mid && !Used[v + N]) Dfs(v + N, Mid, N, M);
    if(v >= M && !Used[v - M]) Dfs(v - M, Mid, N, M);
    Top.pb(v);
}

bool Check(int Mid, int N, int M){
    Top.clear();
    for(int i = 0; i <= Mid; i++){
        Used[i] = 0;
    }
    //return cout << 'h', 0;
    for(int i = 0; i <= Mid; i++){
        if(!Used[i]) Dfs(i, Mid, N, M);
    }
    for(int i = 0; i <= Mid; i++){
        A[Top[i]] = i;
    }
    for(int i = 0; i <= Mid; i++){
        if(i + N <= Mid && A[i] < A[i + N]) return false;
        if(i >= M && A[i] < A[i - M]) return false;
    }
    return true;
}

int main() {
    Kultivator;
    int tt;
    cin >> tt;
    while(tt--){
        int N, M;
        cin >> N >> M;
        int L = 1, R = 4e5 + 1;
        while(L <= R){
            int Mid = (L + R) / 2;
            if(Check(Mid, N, M)) L = Mid + 1;
            else R = Mid - 1;
        }
        Check(R, N, M);
        cout << R << '\n';
        for(int i = 1; i <= R; i++){
            cout << A[i] - A[i - 1] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8552 KB Ok
2 Correct 54 ms 8552 KB Ok
3 Correct 60 ms 2664 KB Ok
4 Correct 51 ms 2664 KB Ok
5 Correct 57 ms 2664 KB Ok
6 Correct 52 ms 3816 KB Ok
7 Correct 51 ms 2536 KB Ok
8 Correct 51 ms 3816 KB Ok
9 Correct 51 ms 2536 KB Ok
10 Correct 56 ms 5396 KB Ok
11 Correct 50 ms 2664 KB Ok
12 Correct 50 ms 2408 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5352 KB Ok
2 Correct 47 ms 5352 KB Ok
3 Correct 56 ms 5352 KB Ok
4 Correct 48 ms 5352 KB Ok
5 Correct 53 ms 5352 KB Ok
6 Correct 54 ms 5480 KB Ok
7 Correct 79 ms 5864 KB Ok
8 Correct 60 ms 5608 KB Ok
9 Correct 76 ms 5992 KB Ok
10 Correct 68 ms 5736 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8552 KB Ok
2 Correct 60 ms 8552 KB Ok
3 Correct 60 ms 5352 KB Ok
4 Correct 51 ms 4328 KB Ok
5 Correct 53 ms 8552 KB Ok
6 Correct 51 ms 8552 KB Ok
7 Correct 56 ms 8552 KB Ok
8 Correct 52 ms 8552 KB Ok
9 Correct 53 ms 8552 KB Ok
10 Correct 50 ms 5352 KB Ok
11 Correct 48 ms 4328 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5352 KB Ok
2 Correct 47 ms 3176 KB Ok
3 Correct 47 ms 2664 KB Ok
4 Correct 46 ms 2812 KB Ok
5 Correct 44 ms 2536 KB Ok
6 Correct 359 ms 10472 KB Ok
7 Correct 297 ms 10600 KB Ok
8 Correct 572 ms 13720 KB Ok
9 Correct 409 ms 12408 KB Ok
10 Correct 243 ms 6632 KB Ok
11 Correct 365 ms 12008 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8552 KB Ok
2 Correct 54 ms 8552 KB Ok
3 Correct 60 ms 2664 KB Ok
4 Correct 51 ms 2664 KB Ok
5 Correct 57 ms 2664 KB Ok
6 Correct 52 ms 3816 KB Ok
7 Correct 51 ms 2536 KB Ok
8 Correct 51 ms 3816 KB Ok
9 Correct 51 ms 2536 KB Ok
10 Correct 56 ms 5396 KB Ok
11 Correct 50 ms 2664 KB Ok
12 Correct 50 ms 2408 KB Ok
13 Correct 24 ms 8552 KB Ok
14 Correct 60 ms 8552 KB Ok
15 Correct 60 ms 5352 KB Ok
16 Correct 51 ms 4328 KB Ok
17 Correct 53 ms 8552 KB Ok
18 Correct 51 ms 8552 KB Ok
19 Correct 56 ms 8552 KB Ok
20 Correct 52 ms 8552 KB Ok
21 Correct 53 ms 8552 KB Ok
22 Correct 50 ms 5352 KB Ok
23 Correct 48 ms 4328 KB Ok
24 Correct 50 ms 2408 KB Ok
25 Correct 54 ms 2360 KB Ok
26 Correct 52 ms 2280 KB Ok
27 Correct 50 ms 2328 KB Ok
28 Correct 49 ms 2280 KB Ok
29 Correct 51 ms 2424 KB Ok
30 Correct 49 ms 2280 KB Ok
31 Correct 52 ms 2280 KB Ok
32 Correct 53 ms 2536 KB Ok
33 Correct 52 ms 2408 KB Ok
34 Correct 55 ms 2536 KB Ok
35 Correct 56 ms 2664 KB Ok
36 Correct 56 ms 2536 KB Ok
37 Correct 55 ms 2536 KB Ok
38 Correct 54 ms 2536 KB Ok
39 Correct 55 ms 2536 KB Ok
40 Correct 56 ms 2536 KB Ok
41 Correct 56 ms 2512 KB Ok
42 Correct 55 ms 2536 KB Ok
43 Correct 55 ms 2536 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8552 KB Ok
2 Correct 54 ms 8552 KB Ok
3 Correct 60 ms 2664 KB Ok
4 Correct 51 ms 2664 KB Ok
5 Correct 57 ms 2664 KB Ok
6 Correct 52 ms 3816 KB Ok
7 Correct 51 ms 2536 KB Ok
8 Correct 51 ms 3816 KB Ok
9 Correct 51 ms 2536 KB Ok
10 Correct 56 ms 5396 KB Ok
11 Correct 50 ms 2664 KB Ok
12 Correct 50 ms 2408 KB Ok
13 Correct 54 ms 5352 KB Ok
14 Correct 47 ms 5352 KB Ok
15 Correct 56 ms 5352 KB Ok
16 Correct 48 ms 5352 KB Ok
17 Correct 53 ms 5352 KB Ok
18 Correct 54 ms 5480 KB Ok
19 Correct 79 ms 5864 KB Ok
20 Correct 60 ms 5608 KB Ok
21 Correct 76 ms 5992 KB Ok
22 Correct 68 ms 5736 KB Ok
23 Correct 24 ms 8552 KB Ok
24 Correct 60 ms 8552 KB Ok
25 Correct 60 ms 5352 KB Ok
26 Correct 51 ms 4328 KB Ok
27 Correct 53 ms 8552 KB Ok
28 Correct 51 ms 8552 KB Ok
29 Correct 56 ms 8552 KB Ok
30 Correct 52 ms 8552 KB Ok
31 Correct 53 ms 8552 KB Ok
32 Correct 50 ms 5352 KB Ok
33 Correct 48 ms 4328 KB Ok
34 Correct 50 ms 2408 KB Ok
35 Correct 54 ms 2360 KB Ok
36 Correct 52 ms 2280 KB Ok
37 Correct 50 ms 2328 KB Ok
38 Correct 49 ms 2280 KB Ok
39 Correct 51 ms 2424 KB Ok
40 Correct 49 ms 2280 KB Ok
41 Correct 52 ms 2280 KB Ok
42 Correct 53 ms 2536 KB Ok
43 Correct 52 ms 2408 KB Ok
44 Correct 55 ms 2536 KB Ok
45 Correct 56 ms 2664 KB Ok
46 Correct 56 ms 2536 KB Ok
47 Correct 55 ms 2536 KB Ok
48 Correct 54 ms 2536 KB Ok
49 Correct 55 ms 2536 KB Ok
50 Correct 56 ms 2536 KB Ok
51 Correct 56 ms 2512 KB Ok
52 Correct 55 ms 2536 KB Ok
53 Correct 55 ms 2536 KB Ok
54 Correct 233 ms 3944 KB Ok
55 Correct 268 ms 4328 KB Ok
56 Correct 258 ms 4200 KB Ok
57 Correct 196 ms 3692 KB Ok
58 Correct 229 ms 3868 KB Ok
59 Correct 218 ms 3688 KB Ok
60 Correct 198 ms 3564 KB Ok
61 Correct 203 ms 3688 KB Ok
62 Correct 264 ms 4072 KB Ok
63 Correct 216 ms 3688 KB Ok
64 Correct 252 ms 4316 KB Ok
65 Correct 239 ms 3944 KB Ok
66 Correct 219 ms 3688 KB Ok
67 Correct 198 ms 3688 KB Ok
68 Correct 221 ms 3868 KB Ok
69 Correct 408 ms 11368 KB Ok
70 Correct 427 ms 12008 KB Ok
71 Correct 396 ms 11448 KB Ok
72 Correct 414 ms 11224 KB Ok
73 Correct 412 ms 11368 KB Ok
74 Correct 402 ms 11268 KB Ok
75 Correct 406 ms 10856 KB Ok
76 Correct 426 ms 11836 KB Ok
77 Correct 404 ms 11112 KB Ok
78 Correct 434 ms 11368 KB Ok
79 Correct 402 ms 11700 KB Ok
80 Correct 418 ms 11680 KB Ok
81 Correct 412 ms 11496 KB Ok
82 Correct 397 ms 11496 KB Ok
83 Correct 394 ms 11112 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8552 KB Ok
2 Correct 54 ms 8552 KB Ok
3 Correct 60 ms 2664 KB Ok
4 Correct 51 ms 2664 KB Ok
5 Correct 57 ms 2664 KB Ok
6 Correct 52 ms 3816 KB Ok
7 Correct 51 ms 2536 KB Ok
8 Correct 51 ms 3816 KB Ok
9 Correct 51 ms 2536 KB Ok
10 Correct 56 ms 5396 KB Ok
11 Correct 50 ms 2664 KB Ok
12 Correct 50 ms 2408 KB Ok
13 Correct 54 ms 5352 KB Ok
14 Correct 47 ms 5352 KB Ok
15 Correct 56 ms 5352 KB Ok
16 Correct 48 ms 5352 KB Ok
17 Correct 53 ms 5352 KB Ok
18 Correct 54 ms 5480 KB Ok
19 Correct 79 ms 5864 KB Ok
20 Correct 60 ms 5608 KB Ok
21 Correct 76 ms 5992 KB Ok
22 Correct 68 ms 5736 KB Ok
23 Correct 24 ms 8552 KB Ok
24 Correct 60 ms 8552 KB Ok
25 Correct 60 ms 5352 KB Ok
26 Correct 51 ms 4328 KB Ok
27 Correct 53 ms 8552 KB Ok
28 Correct 51 ms 8552 KB Ok
29 Correct 56 ms 8552 KB Ok
30 Correct 52 ms 8552 KB Ok
31 Correct 53 ms 8552 KB Ok
32 Correct 50 ms 5352 KB Ok
33 Correct 48 ms 4328 KB Ok
34 Correct 48 ms 5352 KB Ok
35 Correct 47 ms 3176 KB Ok
36 Correct 47 ms 2664 KB Ok
37 Correct 46 ms 2812 KB Ok
38 Correct 44 ms 2536 KB Ok
39 Correct 359 ms 10472 KB Ok
40 Correct 297 ms 10600 KB Ok
41 Correct 572 ms 13720 KB Ok
42 Correct 409 ms 12408 KB Ok
43 Correct 243 ms 6632 KB Ok
44 Correct 365 ms 12008 KB Ok
45 Correct 50 ms 2408 KB Ok
46 Correct 54 ms 2360 KB Ok
47 Correct 52 ms 2280 KB Ok
48 Correct 50 ms 2328 KB Ok
49 Correct 49 ms 2280 KB Ok
50 Correct 51 ms 2424 KB Ok
51 Correct 49 ms 2280 KB Ok
52 Correct 52 ms 2280 KB Ok
53 Correct 53 ms 2536 KB Ok
54 Correct 52 ms 2408 KB Ok
55 Correct 55 ms 2536 KB Ok
56 Correct 56 ms 2664 KB Ok
57 Correct 56 ms 2536 KB Ok
58 Correct 55 ms 2536 KB Ok
59 Correct 54 ms 2536 KB Ok
60 Correct 55 ms 2536 KB Ok
61 Correct 56 ms 2536 KB Ok
62 Correct 56 ms 2512 KB Ok
63 Correct 55 ms 2536 KB Ok
64 Correct 55 ms 2536 KB Ok
65 Correct 233 ms 3944 KB Ok
66 Correct 268 ms 4328 KB Ok
67 Correct 258 ms 4200 KB Ok
68 Correct 196 ms 3692 KB Ok
69 Correct 229 ms 3868 KB Ok
70 Correct 218 ms 3688 KB Ok
71 Correct 198 ms 3564 KB Ok
72 Correct 203 ms 3688 KB Ok
73 Correct 264 ms 4072 KB Ok
74 Correct 216 ms 3688 KB Ok
75 Correct 252 ms 4316 KB Ok
76 Correct 239 ms 3944 KB Ok
77 Correct 219 ms 3688 KB Ok
78 Correct 198 ms 3688 KB Ok
79 Correct 221 ms 3868 KB Ok
80 Correct 408 ms 11368 KB Ok
81 Correct 427 ms 12008 KB Ok
82 Correct 396 ms 11448 KB Ok
83 Correct 414 ms 11224 KB Ok
84 Correct 412 ms 11368 KB Ok
85 Correct 402 ms 11268 KB Ok
86 Correct 406 ms 10856 KB Ok
87 Correct 426 ms 11836 KB Ok
88 Correct 404 ms 11112 KB Ok
89 Correct 434 ms 11368 KB Ok
90 Correct 402 ms 11700 KB Ok
91 Correct 418 ms 11680 KB Ok
92 Correct 412 ms 11496 KB Ok
93 Correct 397 ms 11496 KB Ok
94 Correct 394 ms 11112 KB Ok
95 Correct 527 ms 7396 KB Ok
96 Correct 750 ms 9444 KB Ok
97 Correct 720 ms 8408 KB Ok
98 Correct 534 ms 7652 KB Ok
99 Correct 644 ms 8056 KB Ok
100 Correct 696 ms 8244 KB Ok
101 Correct 673 ms 8428 KB Ok
102 Correct 644 ms 8036 KB Ok
103 Correct 649 ms 8484 KB Ok
104 Correct 771 ms 9700 KB Ok
105 Correct 758 ms 9332 KB Ok
106 Correct 635 ms 9188 KB Ok
107 Correct 759 ms 8932 KB Ok
108 Correct 780 ms 9572 KB Ok
109 Correct 719 ms 9700 KB Ok
110 Correct 1797 ms 41624 KB Ok
111 Correct 1850 ms 44372 KB Ok
112 Correct 1806 ms 44388 KB Ok
113 Correct 1824 ms 43624 KB Ok
114 Correct 1841 ms 45532 KB Ok
115 Correct 1840 ms 43236 KB Ok
116 Correct 1913 ms 44452 KB Ok
117 Correct 1835 ms 43012 KB Ok
118 Correct 1697 ms 43236 KB Ok
119 Correct 1853 ms 42992 KB Ok
120 Correct 1767 ms 43020 KB Ok
121 Correct 1781 ms 41544 KB Ok
122 Correct 1840 ms 44016 KB Ok
123 Correct 1866 ms 44312 KB Ok
124 Correct 1735 ms 41724 KB Ok
125 Correct 1701 ms 26564 KB Ok