oj.uz

Submission #889496

# Submission time Handle Problem Language Result Execution time Memory
889496 2023-12-19T20:30:50 Z makrav Nice sequence (IZhO18_sequence) C++14
0 / 100
 108 ms 81848 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]) {if (M == 2) cout << i << ' ' << g[i][0] << '\n'; bad = true; break; }
            if (g[i][1] != -1 && pos[g[i][1]] < pos[i]) { if (M == 2) cout << i << ' ' << g[i][1] << '\n';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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 78160 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 78164 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 78280 KB Ok
2 Incorrect 69 ms 78336 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 78172 KB Ok
2 Correct 65 ms 78172 KB Ok
3 Correct 66 ms 78172 KB Ok
4 Correct 65 ms 78320 KB Ok
5 Correct 67 ms 78168 KB Ok
6 Incorrect 108 ms 81848 KB Jury has the better answer : jans = 166803, pans = 50000
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 78160 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 78160 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 78160 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -