oj.uz

Submission #379151

# Submission time Handle Problem Language Result Execution time Memory
379151 2021-03-17T10:52:53 Z syl123456 Nice sequence (IZhO18_sequence) C++17
100 / 100
 1835 ms 32868 KB 
#include <bits/stdc++.h>
#define all(i) i.begin(), i.end()
#define rall(i) i.rbegin(), i.rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool check(int n, int m, int len) {
    ++len;
    vector<int> d(len, 0);
    for (int i = n; i < len; ++i) ++d[i];
    for (int i = m; i < len; ++i) ++d[i - m];
    vector<int> stk;
    for (int i = 0; i < len; ++i) if (d[i] == 0) stk.push_back(i);
    while (!stk.empty()) {
        int i = stk.back();
        stk.pop_back();
        if (i + n < len) if (--d[i + n] == 0) stk.push_back(i + n);
        if (i - m >= 0) if (--d[i - m] == 0) stk.push_back(i - m);
    }
    for (int i : d) if (i != 0) return false;
    return true;
}
vector<int> get(int n, int m, int len) {
    ++len;
    vector<int> d(len, 0);
    for (int i = n; i < len; ++i) ++d[i];
    for (int i = m; i < len; ++i) ++d[i - m];
    vector<int> stk, ans(len);
    for (int i = 0; i < len; ++i) if (d[i] == 0) stk.push_back(i);
    int tmp = len;
    while (!stk.empty()) {
        int i = stk.back();
        stk.pop_back();
        ans[i] = tmp--;
        if (i + n < len) if (--d[i + n] == 0) stk.push_back(i + n);
        if (i - m >= 0) if (--d[i - m] == 0) stk.push_back(i - m);
    }
    for (int i = len - 1; i; --i) ans[i] = ans[i] - ans[i - 1];
    return ans;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int l = max(n, m) - 1, r = n + m - 1;
        while (l < r - 1) {
            int mid = l + r >> 1;
            if (check(n, m, mid)) l = mid;
            else r = mid;
        }
        vector<int> ans = get(n, m, l);
        cout << l << '\n';
        for (int i = 1; i <= l; ++i) cout << ans[i] << ' ';
        cout << '\n';
    }
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:50:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 3 ms 492 KB Ok
7 Correct 11 ms 1004 KB Ok
8 Correct 6 ms 620 KB Ok
9 Correct 14 ms 1004 KB Ok
10 Correct 8 ms 748 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 396 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 285 ms 5852 KB Ok
7 Correct 229 ms 3880 KB Ok
8 Correct 498 ms 8212 KB Ok
9 Correct 365 ms 7816 KB Ok
10 Correct 205 ms 3832 KB Ok
11 Correct 357 ms 6824 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 396 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 1 ms 364 KB Ok
19 Correct 1 ms 364 KB Ok
20 Correct 1 ms 364 KB Ok
21 Correct 1 ms 364 KB Ok
22 Correct 1 ms 364 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 4 ms 364 KB Ok
25 Correct 4 ms 364 KB Ok
26 Correct 4 ms 364 KB Ok
27 Correct 4 ms 364 KB Ok
28 Correct 4 ms 364 KB Ok
29 Correct 3 ms 364 KB Ok
30 Correct 3 ms 364 KB Ok
31 Correct 4 ms 364 KB Ok
32 Correct 5 ms 492 KB Ok
33 Correct 4 ms 364 KB Ok
34 Correct 9 ms 492 KB Ok
35 Correct 11 ms 492 KB Ok
36 Correct 9 ms 512 KB Ok
37 Correct 11 ms 492 KB Ok
38 Correct 10 ms 492 KB Ok
39 Correct 9 ms 492 KB Ok
40 Correct 10 ms 620 KB Ok
41 Correct 11 ms 492 KB Ok
42 Correct 9 ms 492 KB Ok
43 Correct 12 ms 492 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 3 ms 492 KB Ok
19 Correct 11 ms 1004 KB Ok
20 Correct 6 ms 620 KB Ok
21 Correct 14 ms 1004 KB Ok
22 Correct 8 ms 748 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 396 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 4 ms 364 KB Ok
35 Correct 4 ms 364 KB Ok
36 Correct 4 ms 364 KB Ok
37 Correct 4 ms 364 KB Ok
38 Correct 4 ms 364 KB Ok
39 Correct 3 ms 364 KB Ok
40 Correct 3 ms 364 KB Ok
41 Correct 4 ms 364 KB Ok
42 Correct 5 ms 492 KB Ok
43 Correct 4 ms 364 KB Ok
44 Correct 9 ms 492 KB Ok
45 Correct 11 ms 492 KB Ok
46 Correct 9 ms 512 KB Ok
47 Correct 11 ms 492 KB Ok
48 Correct 10 ms 492 KB Ok
49 Correct 9 ms 492 KB Ok
50 Correct 10 ms 620 KB Ok
51 Correct 11 ms 492 KB Ok
52 Correct 9 ms 492 KB Ok
53 Correct 12 ms 492 KB Ok
54 Correct 202 ms 2816 KB Ok
55 Correct 263 ms 3404 KB Ok
56 Correct 234 ms 3504 KB Ok
57 Correct 181 ms 2540 KB Ok
58 Correct 209 ms 2964 KB Ok
59 Correct 200 ms 2932 KB Ok
60 Correct 169 ms 2532 KB Ok
61 Correct 174 ms 2656 KB Ok
62 Correct 234 ms 3036 KB Ok
63 Correct 185 ms 2896 KB Ok
64 Correct 241 ms 3328 KB Ok
65 Correct 223 ms 3104 KB Ok
66 Correct 224 ms 2688 KB Ok
67 Correct 174 ms 2644 KB Ok
68 Correct 203 ms 2916 KB Ok
69 Correct 347 ms 7512 KB Ok
70 Correct 373 ms 7784 KB Ok
71 Correct 376 ms 7492 KB Ok
72 Correct 341 ms 7120 KB Ok
73 Correct 349 ms 7524 KB Ok
74 Correct 352 ms 7384 KB Ok
75 Correct 366 ms 7264 KB Ok
76 Correct 395 ms 7568 KB Ok
77 Correct 340 ms 7148 KB Ok
78 Correct 345 ms 7204 KB Ok
79 Correct 346 ms 7576 KB Ok
80 Correct 344 ms 7504 KB Ok
81 Correct 359 ms 7652 KB Ok
82 Correct 352 ms 7676 KB Ok
83 Correct 346 ms 7528 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 3 ms 492 KB Ok
19 Correct 11 ms 1004 KB Ok
20 Correct 6 ms 620 KB Ok
21 Correct 14 ms 1004 KB Ok
22 Correct 8 ms 748 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 396 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 1 ms 364 KB Ok
39 Correct 285 ms 5852 KB Ok
40 Correct 229 ms 3880 KB Ok
41 Correct 498 ms 8212 KB Ok
42 Correct 365 ms 7816 KB Ok
43 Correct 205 ms 3832 KB Ok
44 Correct 357 ms 6824 KB Ok
45 Correct 4 ms 364 KB Ok
46 Correct 4 ms 364 KB Ok
47 Correct 4 ms 364 KB Ok
48 Correct 4 ms 364 KB Ok
49 Correct 4 ms 364 KB Ok
50 Correct 3 ms 364 KB Ok
51 Correct 3 ms 364 KB Ok
52 Correct 4 ms 364 KB Ok
53 Correct 5 ms 492 KB Ok
54 Correct 4 ms 364 KB Ok
55 Correct 9 ms 492 KB Ok
56 Correct 11 ms 492 KB Ok
57 Correct 9 ms 512 KB Ok
58 Correct 11 ms 492 KB Ok
59 Correct 10 ms 492 KB Ok
60 Correct 9 ms 492 KB Ok
61 Correct 10 ms 620 KB Ok
62 Correct 11 ms 492 KB Ok
63 Correct 9 ms 492 KB Ok
64 Correct 12 ms 492 KB Ok
65 Correct 202 ms 2816 KB Ok
66 Correct 263 ms 3404 KB Ok
67 Correct 234 ms 3504 KB Ok
68 Correct 181 ms 2540 KB Ok
69 Correct 209 ms 2964 KB Ok
70 Correct 200 ms 2932 KB Ok
71 Correct 169 ms 2532 KB Ok
72 Correct 174 ms 2656 KB Ok
73 Correct 234 ms 3036 KB Ok
74 Correct 185 ms 2896 KB Ok
75 Correct 241 ms 3328 KB Ok
76 Correct 223 ms 3104 KB Ok
77 Correct 224 ms 2688 KB Ok
78 Correct 174 ms 2644 KB Ok
79 Correct 203 ms 2916 KB Ok
80 Correct 347 ms 7512 KB Ok
81 Correct 373 ms 7784 KB Ok
82 Correct 376 ms 7492 KB Ok
83 Correct 341 ms 7120 KB Ok
84 Correct 349 ms 7524 KB Ok
85 Correct 352 ms 7384 KB Ok
86 Correct 366 ms 7264 KB Ok
87 Correct 395 ms 7568 KB Ok
88 Correct 340 ms 7148 KB Ok
89 Correct 345 ms 7204 KB Ok
90 Correct 346 ms 7576 KB Ok
91 Correct 344 ms 7504 KB Ok
92 Correct 359 ms 7652 KB Ok
93 Correct 352 ms 7676 KB Ok
94 Correct 346 ms 7528 KB Ok
95 Correct 511 ms 7576 KB Ok
96 Correct 803 ms 9960 KB Ok
97 Correct 747 ms 8604 KB Ok
98 Correct 568 ms 7884 KB Ok
99 Correct 673 ms 7924 KB Ok
100 Correct 686 ms 8348 KB Ok
101 Correct 740 ms 8316 KB Ok
102 Correct 681 ms 8664 KB Ok
103 Correct 686 ms 8736 KB Ok
104 Correct 836 ms 10656 KB Ok
105 Correct 759 ms 10804 KB Ok
106 Correct 643 ms 8376 KB Ok
107 Correct 762 ms 8840 KB Ok
108 Correct 807 ms 9604 KB Ok
109 Correct 690 ms 8468 KB Ok
110 Correct 1683 ms 30064 KB Ok
111 Correct 1748 ms 31324 KB Ok
112 Correct 1692 ms 32500 KB Ok
113 Correct 1682 ms 30500 KB Ok
114 Correct 1643 ms 32868 KB Ok
115 Correct 1757 ms 31464 KB Ok
116 Correct 1824 ms 32288 KB Ok
117 Correct 1835 ms 30052 KB Ok
118 Correct 1706 ms 32032 KB Ok
119 Correct 1790 ms 30480 KB Ok
120 Correct 1715 ms 30720 KB Ok
121 Correct 1728 ms 30776 KB Ok
122 Correct 1766 ms 31488 KB Ok
123 Correct 1777 ms 31324 KB Ok
124 Correct 1665 ms 31556 KB Ok
125 Correct 1450 ms 13480 KB Ok