Submission #889498

#	Time	Username	Problem	Language	Result	Execution time	Memory
889498		makrav	Nice sequence (IZhO18_sequence)	C++14	43 / 100	120 ms	81888 KiB

sequence

#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 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 0 / 15
• Subtask 5: 14 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24