oj.uz

Submission #889505

# Submission time Handle Problem Language Result Execution time Memory
889505 2023-12-19T20:39:57 Z makrav Nice sequence (IZhO18_sequence) C++14
100 / 100
 1800 ms 89032 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;

#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld

int g[3000001][2];
int used[3000001], cnt[3000001];
int pos[3000001],ppos[3000001];
int cur = 0, step = 1;

void dfs(int v) {
    used[v] = step;
    if (g[v][0]!=-1&&used[g[v][0]]!=step)dfs(g[v][0]);
    if(g[v][1]!=-1&&used[g[v][1]]!=step)dfs(g[v][1]);
    pos[v] = cur++;
}

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < 3000001; i++) {
        g[i][0] = -1;
        g[i][1] = -1;
        cnt[i] = 0;
    }
    int L = 0, R = 800001;
    while (R - L > 1) {
        int M = (L + R) / 2;
        cur = 0;
        for (int i = 0; i + n <= M; i++) {
            g[i + n][0] = i;
            cnt[i]++;
        }
        for (int i = 0; i + m <= M; i++) {
            g[i][1] = i + m;
            cnt[i + m]++;
        }
        f(i,0,M+1){
            if(used[i]!=step)dfs(i);
        }
        f(i,0,M+1)pos[i] = M - pos[i];
        bool bad = false;
        for (int i = 0; i <= M; i++) {
            if (g[i][0] != -1 && pos[g[i][0]] < pos[i]) { bad = true; break; }
            if (g[i][1] != -1 && pos[g[i][1]] < pos[i]) {bad = true; break; }
        }

        for (int i = 0; i + n <= M; i++) {
            g[i + n][0] = -1;
            cnt[i]--;
        }
        for (int i = 0; i + m <= M; i++) {
            g[i][1] = -1;
            cnt[i + m]--;
        }

        cur = 0;
        step++;
        if (bad) R = M;
        else L = M;
    }
    cout << L << '\n';
    
    int M=L;
    cur = 0;
    for (int i = 0; i + n <= M; i++) {
        g[i + n][0] = i;
        cnt[i]++;
    }
    for (int i = 0; i + m <= M; i++) {
        g[i][1] = i + m;
        cnt[i + m]++;
    }
    //cout << M << '\n';
    f(i, 0, M + 1) {
        if (used[i] != step)dfs(i);
    }
    f(i, 0, M + 1)pos[i] = M - pos[i];
    f(i,0,M+1)ppos[pos[i]] = i;
    vector<int> pref(M+1);
    pref[0]=0;
    for(int j=pos[0]+1;j<=M;j++){
        pref[ppos[j]] = j - pos[0];
    }
    for(int j = pos[0]-1;j>=0;j--){
        pref[ppos[j]]=j-pos[0];
    }
    f(i,1,M+1)cout<<pref[i]-pref[i-1]<<' ';
    cout<<'\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tt; cin >> tt;
    while (tt--) {
        solve();
    }

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 56412 KB Ok
2 Correct 137 ms 56412 KB Ok
3 Correct 138 ms 44740 KB Ok
4 Correct 117 ms 45584 KB Ok
5 Correct 147 ms 44884 KB Ok
6 Correct 140 ms 47152 KB Ok
7 Correct 133 ms 44636 KB Ok
8 Correct 122 ms 47148 KB Ok
9 Correct 126 ms 44724 KB Ok
10 Correct 119 ms 50256 KB Ok
11 Correct 139 ms 44652 KB Ok
12 Correct 112 ms 44380 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 56404 KB Ok
2 Correct 137 ms 56540 KB Ok
3 Correct 134 ms 56404 KB Ok
4 Correct 172 ms 56408 KB Ok
5 Correct 134 ms 56680 KB Ok
6 Correct 135 ms 56412 KB Ok
7 Correct 145 ms 56916 KB Ok
8 Correct 133 ms 56920 KB Ok
9 Correct 186 ms 57020 KB Ok
10 Correct 143 ms 56404 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 56548 KB Ok
2 Correct 162 ms 56540 KB Ok
3 Correct 141 ms 56400 KB Ok
4 Correct 144 ms 56548 KB Ok
5 Correct 170 ms 56544 KB Ok
6 Correct 147 ms 56412 KB Ok
7 Correct 146 ms 56408 KB Ok
8 Correct 169 ms 56600 KB Ok
9 Correct 150 ms 56440 KB Ok
10 Correct 152 ms 56400 KB Ok
11 Correct 150 ms 56544 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 56544 KB Ok
2 Correct 165 ms 56548 KB Ok
3 Correct 158 ms 56412 KB Ok
4 Correct 158 ms 56544 KB Ok
5 Correct 171 ms 56776 KB Ok
6 Correct 341 ms 61636 KB Ok
7 Correct 303 ms 60704 KB Ok
8 Correct 443 ms 64384 KB Ok
9 Correct 379 ms 65300 KB Ok
10 Correct 327 ms 61528 KB Ok
11 Correct 401 ms 63664 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 56412 KB Ok
2 Correct 137 ms 56412 KB Ok
3 Correct 138 ms 44740 KB Ok
4 Correct 117 ms 45584 KB Ok
5 Correct 147 ms 44884 KB Ok
6 Correct 140 ms 47152 KB Ok
7 Correct 133 ms 44636 KB Ok
8 Correct 122 ms 47148 KB Ok
9 Correct 126 ms 44724 KB Ok
10 Correct 119 ms 50256 KB Ok
11 Correct 139 ms 44652 KB Ok
12 Correct 112 ms 44380 KB Ok
13 Correct 64 ms 56548 KB Ok
14 Correct 162 ms 56540 KB Ok
15 Correct 141 ms 56400 KB Ok
16 Correct 144 ms 56548 KB Ok
17 Correct 170 ms 56544 KB Ok
18 Correct 147 ms 56412 KB Ok
19 Correct 146 ms 56408 KB Ok
20 Correct 169 ms 56600 KB Ok
21 Correct 150 ms 56440 KB Ok
22 Correct 152 ms 56400 KB Ok
23 Correct 150 ms 56544 KB Ok
24 Correct 142 ms 44116 KB Ok
25 Correct 150 ms 44324 KB Ok
26 Correct 149 ms 45184 KB Ok
27 Correct 140 ms 45068 KB Ok
28 Correct 152 ms 44116 KB Ok
29 Correct 143 ms 48192 KB Ok
30 Correct 135 ms 44628 KB Ok
31 Correct 137 ms 44116 KB Ok
32 Correct 143 ms 44184 KB Ok
33 Correct 139 ms 44616 KB Ok
34 Correct 221 ms 56404 KB Ok
35 Correct 183 ms 56656 KB Ok
36 Correct 198 ms 56952 KB Ok
37 Correct 182 ms 56668 KB Ok
38 Correct 181 ms 56564 KB Ok
39 Correct 216 ms 56560 KB Ok
40 Correct 199 ms 56412 KB Ok
41 Correct 194 ms 56568 KB Ok
42 Correct 186 ms 56804 KB Ok
43 Correct 203 ms 56660 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 56412 KB Ok
2 Correct 137 ms 56412 KB Ok
3 Correct 138 ms 44740 KB Ok
4 Correct 117 ms 45584 KB Ok
5 Correct 147 ms 44884 KB Ok
6 Correct 140 ms 47152 KB Ok
7 Correct 133 ms 44636 KB Ok
8 Correct 122 ms 47148 KB Ok
9 Correct 126 ms 44724 KB Ok
10 Correct 119 ms 50256 KB Ok
11 Correct 139 ms 44652 KB Ok
12 Correct 112 ms 44380 KB Ok
13 Correct 159 ms 56404 KB Ok
14 Correct 137 ms 56540 KB Ok
15 Correct 134 ms 56404 KB Ok
16 Correct 172 ms 56408 KB Ok
17 Correct 134 ms 56680 KB Ok
18 Correct 135 ms 56412 KB Ok
19 Correct 145 ms 56916 KB Ok
20 Correct 133 ms 56920 KB Ok
21 Correct 186 ms 57020 KB Ok
22 Correct 143 ms 56404 KB Ok
23 Correct 64 ms 56548 KB Ok
24 Correct 162 ms 56540 KB Ok
25 Correct 141 ms 56400 KB Ok
26 Correct 144 ms 56548 KB Ok
27 Correct 170 ms 56544 KB Ok
28 Correct 147 ms 56412 KB Ok
29 Correct 146 ms 56408 KB Ok
30 Correct 169 ms 56600 KB Ok
31 Correct 150 ms 56440 KB Ok
32 Correct 152 ms 56400 KB Ok
33 Correct 150 ms 56544 KB Ok
34 Correct 142 ms 44116 KB Ok
35 Correct 150 ms 44324 KB Ok
36 Correct 149 ms 45184 KB Ok
37 Correct 140 ms 45068 KB Ok
38 Correct 152 ms 44116 KB Ok
39 Correct 143 ms 48192 KB Ok
40 Correct 135 ms 44628 KB Ok
41 Correct 137 ms 44116 KB Ok
42 Correct 143 ms 44184 KB Ok
43 Correct 139 ms 44616 KB Ok
44 Correct 221 ms 56404 KB Ok
45 Correct 183 ms 56656 KB Ok
46 Correct 198 ms 56952 KB Ok
47 Correct 182 ms 56668 KB Ok
48 Correct 181 ms 56564 KB Ok
49 Correct 216 ms 56560 KB Ok
50 Correct 199 ms 56412 KB Ok
51 Correct 194 ms 56568 KB Ok
52 Correct 186 ms 56804 KB Ok
53 Correct 203 ms 56660 KB Ok
54 Correct 209 ms 48600 KB Ok
55 Correct 247 ms 49068 KB Ok
56 Correct 226 ms 48980 KB Ok
57 Correct 186 ms 48244 KB Ok
58 Correct 222 ms 48992 KB Ok
59 Correct 215 ms 49036 KB Ok
60 Correct 191 ms 48408 KB Ok
61 Correct 192 ms 48444 KB Ok
62 Correct 262 ms 49160 KB Ok
63 Correct 210 ms 48560 KB Ok
64 Correct 232 ms 49120 KB Ok
65 Correct 216 ms 49044 KB Ok
66 Correct 202 ms 48680 KB Ok
67 Correct 189 ms 48352 KB Ok
68 Correct 228 ms 48840 KB Ok
69 Correct 528 ms 62080 KB Ok
70 Correct 501 ms 65504 KB Ok
71 Correct 533 ms 62144 KB Ok
72 Correct 472 ms 65076 KB Ok
73 Correct 555 ms 62400 KB Ok
74 Correct 482 ms 61884 KB Ok
75 Correct 502 ms 61996 KB Ok
76 Correct 517 ms 65296 KB Ok
77 Correct 521 ms 62244 KB Ok
78 Correct 555 ms 65040 KB Ok
79 Correct 511 ms 65460 KB Ok
80 Correct 501 ms 65088 KB Ok
81 Correct 516 ms 65468 KB Ok
82 Correct 524 ms 65184 KB Ok
83 Correct 520 ms 62196 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 56412 KB Ok
2 Correct 137 ms 56412 KB Ok
3 Correct 138 ms 44740 KB Ok
4 Correct 117 ms 45584 KB Ok
5 Correct 147 ms 44884 KB Ok
6 Correct 140 ms 47152 KB Ok
7 Correct 133 ms 44636 KB Ok
8 Correct 122 ms 47148 KB Ok
9 Correct 126 ms 44724 KB Ok
10 Correct 119 ms 50256 KB Ok
11 Correct 139 ms 44652 KB Ok
12 Correct 112 ms 44380 KB Ok
13 Correct 159 ms 56404 KB Ok
14 Correct 137 ms 56540 KB Ok
15 Correct 134 ms 56404 KB Ok
16 Correct 172 ms 56408 KB Ok
17 Correct 134 ms 56680 KB Ok
18 Correct 135 ms 56412 KB Ok
19 Correct 145 ms 56916 KB Ok
20 Correct 133 ms 56920 KB Ok
21 Correct 186 ms 57020 KB Ok
22 Correct 143 ms 56404 KB Ok
23 Correct 64 ms 56548 KB Ok
24 Correct 162 ms 56540 KB Ok
25 Correct 141 ms 56400 KB Ok
26 Correct 144 ms 56548 KB Ok
27 Correct 170 ms 56544 KB Ok
28 Correct 147 ms 56412 KB Ok
29 Correct 146 ms 56408 KB Ok
30 Correct 169 ms 56600 KB Ok
31 Correct 150 ms 56440 KB Ok
32 Correct 152 ms 56400 KB Ok
33 Correct 150 ms 56544 KB Ok
34 Correct 163 ms 56544 KB Ok
35 Correct 165 ms 56548 KB Ok
36 Correct 158 ms 56412 KB Ok
37 Correct 158 ms 56544 KB Ok
38 Correct 171 ms 56776 KB Ok
39 Correct 341 ms 61636 KB Ok
40 Correct 303 ms 60704 KB Ok
41 Correct 443 ms 64384 KB Ok
42 Correct 379 ms 65300 KB Ok
43 Correct 327 ms 61528 KB Ok
44 Correct 401 ms 63664 KB Ok
45 Correct 142 ms 44116 KB Ok
46 Correct 150 ms 44324 KB Ok
47 Correct 149 ms 45184 KB Ok
48 Correct 140 ms 45068 KB Ok
49 Correct 152 ms 44116 KB Ok
50 Correct 143 ms 48192 KB Ok
51 Correct 135 ms 44628 KB Ok
52 Correct 137 ms 44116 KB Ok
53 Correct 143 ms 44184 KB Ok
54 Correct 139 ms 44616 KB Ok
55 Correct 221 ms 56404 KB Ok
56 Correct 183 ms 56656 KB Ok
57 Correct 198 ms 56952 KB Ok
58 Correct 182 ms 56668 KB Ok
59 Correct 181 ms 56564 KB Ok
60 Correct 216 ms 56560 KB Ok
61 Correct 199 ms 56412 KB Ok
62 Correct 194 ms 56568 KB Ok
63 Correct 186 ms 56804 KB Ok
64 Correct 203 ms 56660 KB Ok
65 Correct 209 ms 48600 KB Ok
66 Correct 247 ms 49068 KB Ok
67 Correct 226 ms 48980 KB Ok
68 Correct 186 ms 48244 KB Ok
69 Correct 222 ms 48992 KB Ok
70 Correct 215 ms 49036 KB Ok
71 Correct 191 ms 48408 KB Ok
72 Correct 192 ms 48444 KB Ok
73 Correct 262 ms 49160 KB Ok
74 Correct 210 ms 48560 KB Ok
75 Correct 232 ms 49120 KB Ok
76 Correct 216 ms 49044 KB Ok
77 Correct 202 ms 48680 KB Ok
78 Correct 189 ms 48352 KB Ok
79 Correct 228 ms 48840 KB Ok
80 Correct 528 ms 62080 KB Ok
81 Correct 501 ms 65504 KB Ok
82 Correct 533 ms 62144 KB Ok
83 Correct 472 ms 65076 KB Ok
84 Correct 555 ms 62400 KB Ok
85 Correct 482 ms 61884 KB Ok
86 Correct 502 ms 61996 KB Ok
87 Correct 517 ms 65296 KB Ok
88 Correct 521 ms 62244 KB Ok
89 Correct 555 ms 65040 KB Ok
90 Correct 511 ms 65460 KB Ok
91 Correct 501 ms 65088 KB Ok
92 Correct 516 ms 65468 KB Ok
93 Correct 524 ms 65184 KB Ok
94 Correct 520 ms 62196 KB Ok
95 Correct 374 ms 52636 KB Ok
96 Correct 504 ms 56548 KB Ok
97 Correct 515 ms 55072 KB Ok
98 Correct 371 ms 52888 KB Ok
99 Correct 430 ms 53784 KB Ok
100 Correct 497 ms 54972 KB Ok
101 Correct 453 ms 54220 KB Ok
102 Correct 451 ms 54764 KB Ok
103 Correct 453 ms 54972 KB Ok
104 Correct 505 ms 55724 KB Ok
105 Correct 484 ms 56868 KB Ok
106 Correct 432 ms 54228 KB Ok
107 Correct 470 ms 55156 KB Ok
108 Correct 527 ms 56052 KB Ok
109 Correct 500 ms 54968 KB Ok
110 Correct 1603 ms 86208 KB Ok
111 Correct 1741 ms 88040 KB Ok
112 Correct 1694 ms 88340 KB Ok
113 Correct 1800 ms 87008 KB Ok
114 Correct 1589 ms 89032 KB Ok
115 Correct 1697 ms 88100 KB Ok
116 Correct 1777 ms 88660 KB Ok
117 Correct 1769 ms 87372 KB Ok
118 Correct 1645 ms 88976 KB Ok
119 Correct 1757 ms 87008 KB Ok
120 Correct 1795 ms 87432 KB Ok
121 Correct 1717 ms 86876 KB Ok
122 Correct 1720 ms 87768 KB Ok
123 Correct 1800 ms 87964 KB Ok
124 Correct 1630 ms 88928 KB Ok
125 Correct 1179 ms 70356 KB Ok