oj.uz

Submission #889500

# Submission time Handle Problem Language Result Execution time Memory
889500 2023-12-19T20:34:37 Z makrav Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 124808 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
#define int ll

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 = 1000001;
    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]++;
        }
        //cout << M << '\n';
        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 266 ms 99660 KB Ok
2 Correct 227 ms 99672 KB Ok
3 Correct 217 ms 85432 KB Ok
4 Correct 233 ms 86028 KB Ok
5 Correct 255 ms 85076 KB Ok
6 Correct 225 ms 87900 KB Ok
7 Correct 237 ms 84704 KB Ok
8 Correct 213 ms 87912 KB Ok
9 Correct 235 ms 84836 KB Ok
10 Correct 250 ms 91704 KB Ok
11 Correct 260 ms 84788 KB Ok
12 Correct 251 ms 84488 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 99412 KB Ok
2 Correct 226 ms 99656 KB Ok
3 Correct 278 ms 99660 KB Ok
4 Correct 229 ms 99660 KB Ok
5 Correct 254 ms 99664 KB Ok
6 Correct 211 ms 99660 KB Ok
7 Correct 224 ms 99908 KB Ok
8 Correct 252 ms 99940 KB Ok
9 Correct 263 ms 100068 KB Ok
10 Correct 238 ms 99664 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 99672 KB Ok
2 Correct 225 ms 99676 KB Ok
3 Correct 230 ms 99664 KB Ok
4 Correct 238 ms 99412 KB Ok
5 Correct 230 ms 99660 KB Ok
6 Correct 238 ms 99676 KB Ok
7 Correct 228 ms 99416 KB Ok
8 Correct 248 ms 99780 KB Ok
9 Correct 236 ms 99412 KB Ok
10 Correct 240 ms 99660 KB Ok
11 Correct 230 ms 99660 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 99412 KB Ok
2 Correct 248 ms 99672 KB Ok
3 Correct 245 ms 99676 KB Ok
4 Correct 266 ms 99672 KB Ok
5 Correct 263 ms 99412 KB Ok
6 Correct 410 ms 105516 KB Ok
7 Correct 392 ms 104556 KB Ok
8 Correct 525 ms 107584 KB Ok
9 Correct 466 ms 108584 KB Ok
10 Correct 396 ms 105136 KB Ok
11 Correct 525 ms 107712 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 99660 KB Ok
2 Correct 227 ms 99672 KB Ok
3 Correct 217 ms 85432 KB Ok
4 Correct 233 ms 86028 KB Ok
5 Correct 255 ms 85076 KB Ok
6 Correct 225 ms 87900 KB Ok
7 Correct 237 ms 84704 KB Ok
8 Correct 213 ms 87912 KB Ok
9 Correct 235 ms 84836 KB Ok
10 Correct 250 ms 91704 KB Ok
11 Correct 260 ms 84788 KB Ok
12 Correct 251 ms 84488 KB Ok
13 Correct 75 ms 99672 KB Ok
14 Correct 225 ms 99676 KB Ok
15 Correct 230 ms 99664 KB Ok
16 Correct 238 ms 99412 KB Ok
17 Correct 230 ms 99660 KB Ok
18 Correct 238 ms 99676 KB Ok
19 Correct 228 ms 99416 KB Ok
20 Correct 248 ms 99780 KB Ok
21 Correct 236 ms 99412 KB Ok
22 Correct 240 ms 99660 KB Ok
23 Correct 230 ms 99660 KB Ok
24 Correct 211 ms 84056 KB Ok
25 Correct 245 ms 84568 KB Ok
26 Correct 232 ms 85084 KB Ok
27 Correct 246 ms 85552 KB Ok
28 Correct 241 ms 84304 KB Ok
29 Correct 231 ms 89260 KB Ok
30 Correct 236 ms 84824 KB Ok
31 Correct 251 ms 84356 KB Ok
32 Correct 260 ms 84308 KB Ok
33 Correct 241 ms 84820 KB Ok
34 Correct 423 ms 99728 KB Ok
35 Correct 358 ms 99644 KB Ok
36 Correct 443 ms 99920 KB Ok
37 Correct 321 ms 99648 KB Ok
38 Correct 339 ms 99712 KB Ok
39 Correct 372 ms 99736 KB Ok
40 Correct 384 ms 99728 KB Ok
41 Correct 315 ms 99684 KB Ok
42 Correct 394 ms 100260 KB Ok
43 Correct 352 ms 99736 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 99660 KB Ok
2 Correct 227 ms 99672 KB Ok
3 Correct 217 ms 85432 KB Ok
4 Correct 233 ms 86028 KB Ok
5 Correct 255 ms 85076 KB Ok
6 Correct 225 ms 87900 KB Ok
7 Correct 237 ms 84704 KB Ok
8 Correct 213 ms 87912 KB Ok
9 Correct 235 ms 84836 KB Ok
10 Correct 250 ms 91704 KB Ok
11 Correct 260 ms 84788 KB Ok
12 Correct 251 ms 84488 KB Ok
13 Correct 261 ms 99412 KB Ok
14 Correct 226 ms 99656 KB Ok
15 Correct 278 ms 99660 KB Ok
16 Correct 229 ms 99660 KB Ok
17 Correct 254 ms 99664 KB Ok
18 Correct 211 ms 99660 KB Ok
19 Correct 224 ms 99908 KB Ok
20 Correct 252 ms 99940 KB Ok
21 Correct 263 ms 100068 KB Ok
22 Correct 238 ms 99664 KB Ok
23 Correct 75 ms 99672 KB Ok
24 Correct 225 ms 99676 KB Ok
25 Correct 230 ms 99664 KB Ok
26 Correct 238 ms 99412 KB Ok
27 Correct 230 ms 99660 KB Ok
28 Correct 238 ms 99676 KB Ok
29 Correct 228 ms 99416 KB Ok
30 Correct 248 ms 99780 KB Ok
31 Correct 236 ms 99412 KB Ok
32 Correct 240 ms 99660 KB Ok
33 Correct 230 ms 99660 KB Ok
34 Correct 211 ms 84056 KB Ok
35 Correct 245 ms 84568 KB Ok
36 Correct 232 ms 85084 KB Ok
37 Correct 246 ms 85552 KB Ok
38 Correct 241 ms 84304 KB Ok
39 Correct 231 ms 89260 KB Ok
40 Correct 236 ms 84824 KB Ok
41 Correct 251 ms 84356 KB Ok
42 Correct 260 ms 84308 KB Ok
43 Correct 241 ms 84820 KB Ok
44 Correct 423 ms 99728 KB Ok
45 Correct 358 ms 99644 KB Ok
46 Correct 443 ms 99920 KB Ok
47 Correct 321 ms 99648 KB Ok
48 Correct 339 ms 99712 KB Ok
49 Correct 372 ms 99736 KB Ok
50 Correct 384 ms 99728 KB Ok
51 Correct 315 ms 99684 KB Ok
52 Correct 394 ms 100260 KB Ok
53 Correct 352 ms 99736 KB Ok
54 Correct 279 ms 89032 KB Ok
55 Correct 284 ms 89504 KB Ok
56 Correct 287 ms 89460 KB Ok
57 Correct 232 ms 88524 KB Ok
58 Correct 289 ms 89248 KB Ok
59 Correct 262 ms 89236 KB Ok
60 Correct 254 ms 88896 KB Ok
61 Correct 250 ms 88688 KB Ok
62 Correct 304 ms 89700 KB Ok
63 Correct 260 ms 88912 KB Ok
64 Correct 350 ms 89472 KB Ok
65 Correct 273 ms 89336 KB Ok
66 Correct 258 ms 88948 KB Ok
67 Correct 270 ms 88912 KB Ok
68 Correct 279 ms 89128 KB Ok
69 Correct 701 ms 105504 KB Ok
70 Correct 712 ms 108928 KB Ok
71 Correct 740 ms 105652 KB Ok
72 Correct 647 ms 108652 KB Ok
73 Correct 684 ms 105776 KB Ok
74 Correct 753 ms 105568 KB Ok
75 Correct 735 ms 105780 KB Ok
76 Correct 737 ms 108860 KB Ok
77 Correct 675 ms 105508 KB Ok
78 Correct 672 ms 108456 KB Ok
79 Correct 738 ms 109200 KB Ok
80 Correct 687 ms 108536 KB Ok
81 Correct 691 ms 108964 KB Ok
82 Correct 694 ms 108752 KB Ok
83 Correct 694 ms 106192 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 99660 KB Ok
2 Correct 227 ms 99672 KB Ok
3 Correct 217 ms 85432 KB Ok
4 Correct 233 ms 86028 KB Ok
5 Correct 255 ms 85076 KB Ok
6 Correct 225 ms 87900 KB Ok
7 Correct 237 ms 84704 KB Ok
8 Correct 213 ms 87912 KB Ok
9 Correct 235 ms 84836 KB Ok
10 Correct 250 ms 91704 KB Ok
11 Correct 260 ms 84788 KB Ok
12 Correct 251 ms 84488 KB Ok
13 Correct 261 ms 99412 KB Ok
14 Correct 226 ms 99656 KB Ok
15 Correct 278 ms 99660 KB Ok
16 Correct 229 ms 99660 KB Ok
17 Correct 254 ms 99664 KB Ok
18 Correct 211 ms 99660 KB Ok
19 Correct 224 ms 99908 KB Ok
20 Correct 252 ms 99940 KB Ok
21 Correct 263 ms 100068 KB Ok
22 Correct 238 ms 99664 KB Ok
23 Correct 75 ms 99672 KB Ok
24 Correct 225 ms 99676 KB Ok
25 Correct 230 ms 99664 KB Ok
26 Correct 238 ms 99412 KB Ok
27 Correct 230 ms 99660 KB Ok
28 Correct 238 ms 99676 KB Ok
29 Correct 228 ms 99416 KB Ok
30 Correct 248 ms 99780 KB Ok
31 Correct 236 ms 99412 KB Ok
32 Correct 240 ms 99660 KB Ok
33 Correct 230 ms 99660 KB Ok
34 Correct 249 ms 99412 KB Ok
35 Correct 248 ms 99672 KB Ok
36 Correct 245 ms 99676 KB Ok
37 Correct 266 ms 99672 KB Ok
38 Correct 263 ms 99412 KB Ok
39 Correct 410 ms 105516 KB Ok
40 Correct 392 ms 104556 KB Ok
41 Correct 525 ms 107584 KB Ok
42 Correct 466 ms 108584 KB Ok
43 Correct 396 ms 105136 KB Ok
44 Correct 525 ms 107712 KB Ok
45 Correct 211 ms 84056 KB Ok
46 Correct 245 ms 84568 KB Ok
47 Correct 232 ms 85084 KB Ok
48 Correct 246 ms 85552 KB Ok
49 Correct 241 ms 84304 KB Ok
50 Correct 231 ms 89260 KB Ok
51 Correct 236 ms 84824 KB Ok
52 Correct 251 ms 84356 KB Ok
53 Correct 260 ms 84308 KB Ok
54 Correct 241 ms 84820 KB Ok
55 Correct 423 ms 99728 KB Ok
56 Correct 358 ms 99644 KB Ok
57 Correct 443 ms 99920 KB Ok
58 Correct 321 ms 99648 KB Ok
59 Correct 339 ms 99712 KB Ok
60 Correct 372 ms 99736 KB Ok
61 Correct 384 ms 99728 KB Ok
62 Correct 315 ms 99684 KB Ok
63 Correct 394 ms 100260 KB Ok
64 Correct 352 ms 99736 KB Ok
65 Correct 279 ms 89032 KB Ok
66 Correct 284 ms 89504 KB Ok
67 Correct 287 ms 89460 KB Ok
68 Correct 232 ms 88524 KB Ok
69 Correct 289 ms 89248 KB Ok
70 Correct 262 ms 89236 KB Ok
71 Correct 254 ms 88896 KB Ok
72 Correct 250 ms 88688 KB Ok
73 Correct 304 ms 89700 KB Ok
74 Correct 260 ms 88912 KB Ok
75 Correct 350 ms 89472 KB Ok
76 Correct 273 ms 89336 KB Ok
77 Correct 258 ms 88948 KB Ok
78 Correct 270 ms 88912 KB Ok
79 Correct 279 ms 89128 KB Ok
80 Correct 701 ms 105504 KB Ok
81 Correct 712 ms 108928 KB Ok
82 Correct 740 ms 105652 KB Ok
83 Correct 647 ms 108652 KB Ok
84 Correct 684 ms 105776 KB Ok
85 Correct 753 ms 105568 KB Ok
86 Correct 735 ms 105780 KB Ok
87 Correct 737 ms 108860 KB Ok
88 Correct 675 ms 105508 KB Ok
89 Correct 672 ms 108456 KB Ok
90 Correct 738 ms 109200 KB Ok
91 Correct 687 ms 108536 KB Ok
92 Correct 691 ms 108964 KB Ok
93 Correct 694 ms 108752 KB Ok
94 Correct 694 ms 106192 KB Ok
95 Correct 434 ms 93660 KB Ok
96 Correct 546 ms 101436 KB Ok
97 Correct 525 ms 96212 KB Ok
98 Correct 402 ms 95872 KB Ok
99 Correct 473 ms 94840 KB Ok
100 Correct 522 ms 96184 KB Ok
101 Correct 500 ms 97344 KB Ok
102 Correct 559 ms 97720 KB Ok
103 Correct 494 ms 97932 KB Ok
104 Correct 559 ms 99044 KB Ok
105 Correct 578 ms 101548 KB Ok
106 Correct 467 ms 97360 KB Ok
107 Correct 544 ms 98484 KB Ok
108 Correct 585 ms 100356 KB Ok
109 Correct 546 ms 98348 KB Ok
110 Execution timed out 2037 ms 124808 KB Time limit exceeded
111 Halted 0 ms 0 KB -