oj.uz

Submission #889498

# Submission time Handle Problem Language Result Execution time Memory
889498 2023-12-19T20:32:31 Z makrav Nice sequence (IZhO18_sequence) C++14
43 / 100
 120 ms 81888 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 = 50001;
    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 66 ms 78324 KB Ok
2 Correct 73 ms 78316 KB Ok
3 Correct 67 ms 77404 KB Ok
4 Correct 71 ms 77656 KB Ok
5 Correct 67 ms 77592 KB Ok
6 Correct 64 ms 77648 KB Ok
7 Correct 68 ms 77592 KB Ok
8 Correct 64 ms 77656 KB Ok
9 Correct 66 ms 77668 KB Ok
10 Correct 65 ms 77904 KB Ok
11 Correct 67 ms 77576 KB Ok
12 Correct 65 ms 77404 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78320 KB Ok
2 Correct 66 ms 78212 KB Ok
3 Correct 67 ms 78168 KB Ok
4 Correct 68 ms 78172 KB Ok
5 Correct 67 ms 78172 KB Ok
6 Correct 69 ms 78416 KB Ok
7 Correct 77 ms 78484 KB Ok
8 Correct 71 ms 78416 KB Ok
9 Correct 82 ms 78680 KB Ok
10 Correct 82 ms 78316 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 78332 KB Ok
2 Correct 68 ms 78312 KB Ok
3 Correct 65 ms 78260 KB Ok
4 Correct 66 ms 78320 KB Ok
5 Correct 70 ms 78168 KB Ok
6 Correct 67 ms 78316 KB Ok
7 Correct 66 ms 78172 KB Ok
8 Correct 65 ms 78172 KB Ok
9 Correct 66 ms 78272 KB Ok
10 Correct 68 ms 78544 KB Ok
11 Correct 66 ms 78164 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78172 KB Ok
2 Correct 67 ms 78172 KB Ok
3 Correct 71 ms 78168 KB Ok
4 Correct 72 ms 78172 KB Ok
5 Correct 65 ms 78336 KB Ok
6 Incorrect 109 ms 81888 KB Jury has the better answer : jans = 166803, pans = 50000
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78324 KB Ok
2 Correct 73 ms 78316 KB Ok
3 Correct 67 ms 77404 KB Ok
4 Correct 71 ms 77656 KB Ok
5 Correct 67 ms 77592 KB Ok
6 Correct 64 ms 77648 KB Ok
7 Correct 68 ms 77592 KB Ok
8 Correct 64 ms 77656 KB Ok
9 Correct 66 ms 77668 KB Ok
10 Correct 65 ms 77904 KB Ok
11 Correct 67 ms 77576 KB Ok
12 Correct 65 ms 77404 KB Ok
13 Correct 27 ms 78332 KB Ok
14 Correct 68 ms 78312 KB Ok
15 Correct 65 ms 78260 KB Ok
16 Correct 66 ms 78320 KB Ok
17 Correct 70 ms 78168 KB Ok
18 Correct 67 ms 78316 KB Ok
19 Correct 66 ms 78172 KB Ok
20 Correct 65 ms 78172 KB Ok
21 Correct 66 ms 78272 KB Ok
22 Correct 68 ms 78544 KB Ok
23 Correct 66 ms 78164 KB Ok
24 Correct 68 ms 77588 KB Ok
25 Correct 76 ms 77632 KB Ok
26 Correct 68 ms 77648 KB Ok
27 Correct 67 ms 77660 KB Ok
28 Correct 70 ms 77624 KB Ok
29 Correct 65 ms 77604 KB Ok
30 Correct 69 ms 77652 KB Ok
31 Correct 71 ms 77608 KB Ok
32 Correct 67 ms 77404 KB Ok
33 Correct 76 ms 77664 KB Ok
34 Correct 81 ms 78160 KB Ok
35 Correct 77 ms 78472 KB Ok
36 Correct 75 ms 78396 KB Ok
37 Correct 74 ms 78496 KB Ok
38 Correct 76 ms 78416 KB Ok
39 Correct 75 ms 78380 KB Ok
40 Correct 80 ms 78296 KB Ok
41 Correct 76 ms 78416 KB Ok
42 Correct 77 ms 78416 KB Ok
43 Correct 73 ms 78416 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78324 KB Ok
2 Correct 73 ms 78316 KB Ok
3 Correct 67 ms 77404 KB Ok
4 Correct 71 ms 77656 KB Ok
5 Correct 67 ms 77592 KB Ok
6 Correct 64 ms 77648 KB Ok
7 Correct 68 ms 77592 KB Ok
8 Correct 64 ms 77656 KB Ok
9 Correct 66 ms 77668 KB Ok
10 Correct 65 ms 77904 KB Ok
11 Correct 67 ms 77576 KB Ok
12 Correct 65 ms 77404 KB Ok
13 Correct 66 ms 78320 KB Ok
14 Correct 66 ms 78212 KB Ok
15 Correct 67 ms 78168 KB Ok
16 Correct 68 ms 78172 KB Ok
17 Correct 67 ms 78172 KB Ok
18 Correct 69 ms 78416 KB Ok
19 Correct 77 ms 78484 KB Ok
20 Correct 71 ms 78416 KB Ok
21 Correct 82 ms 78680 KB Ok
22 Correct 82 ms 78316 KB Ok
23 Correct 27 ms 78332 KB Ok
24 Correct 68 ms 78312 KB Ok
25 Correct 65 ms 78260 KB Ok
26 Correct 66 ms 78320 KB Ok
27 Correct 70 ms 78168 KB Ok
28 Correct 67 ms 78316 KB Ok
29 Correct 66 ms 78172 KB Ok
30 Correct 65 ms 78172 KB Ok
31 Correct 66 ms 78272 KB Ok
32 Correct 68 ms 78544 KB Ok
33 Correct 66 ms 78164 KB Ok
34 Correct 68 ms 77588 KB Ok
35 Correct 76 ms 77632 KB Ok
36 Correct 68 ms 77648 KB Ok
37 Correct 67 ms 77660 KB Ok
38 Correct 70 ms 77624 KB Ok
39 Correct 65 ms 77604 KB Ok
40 Correct 69 ms 77652 KB Ok
41 Correct 71 ms 77608 KB Ok
42 Correct 67 ms 77404 KB Ok
43 Correct 76 ms 77664 KB Ok
44 Correct 81 ms 78160 KB Ok
45 Correct 77 ms 78472 KB Ok
46 Correct 75 ms 78396 KB Ok
47 Correct 74 ms 78496 KB Ok
48 Correct 76 ms 78416 KB Ok
49 Correct 75 ms 78380 KB Ok
50 Correct 80 ms 78296 KB Ok
51 Correct 76 ms 78416 KB Ok
52 Correct 77 ms 78416 KB Ok
53 Correct 73 ms 78416 KB Ok
54 Incorrect 120 ms 81772 KB Jury has the better answer : jans = 82899, pans = 50000
55 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78324 KB Ok
2 Correct 73 ms 78316 KB Ok
3 Correct 67 ms 77404 KB Ok
4 Correct 71 ms 77656 KB Ok
5 Correct 67 ms 77592 KB Ok
6 Correct 64 ms 77648 KB Ok
7 Correct 68 ms 77592 KB Ok
8 Correct 64 ms 77656 KB Ok
9 Correct 66 ms 77668 KB Ok
10 Correct 65 ms 77904 KB Ok
11 Correct 67 ms 77576 KB Ok
12 Correct 65 ms 77404 KB Ok
13 Correct 66 ms 78320 KB Ok
14 Correct 66 ms 78212 KB Ok
15 Correct 67 ms 78168 KB Ok
16 Correct 68 ms 78172 KB Ok
17 Correct 67 ms 78172 KB Ok
18 Correct 69 ms 78416 KB Ok
19 Correct 77 ms 78484 KB Ok
20 Correct 71 ms 78416 KB Ok
21 Correct 82 ms 78680 KB Ok
22 Correct 82 ms 78316 KB Ok
23 Correct 27 ms 78332 KB Ok
24 Correct 68 ms 78312 KB Ok
25 Correct 65 ms 78260 KB Ok
26 Correct 66 ms 78320 KB Ok
27 Correct 70 ms 78168 KB Ok
28 Correct 67 ms 78316 KB Ok
29 Correct 66 ms 78172 KB Ok
30 Correct 65 ms 78172 KB Ok
31 Correct 66 ms 78272 KB Ok
32 Correct 68 ms 78544 KB Ok
33 Correct 66 ms 78164 KB Ok
34 Correct 67 ms 78172 KB Ok
35 Correct 67 ms 78172 KB Ok
36 Correct 71 ms 78168 KB Ok
37 Correct 72 ms 78172 KB Ok
38 Correct 65 ms 78336 KB Ok
39 Incorrect 109 ms 81888 KB Jury has the better answer : jans = 166803, pans = 50000
40 Halted 0 ms 0 KB -