oj.uz

Submission #865801

# Submission time Handle Problem Language Result Execution time Memory
865801 2023-10-24T16:41:16 Z azimanov Sequence (BOI14_sequence) C++17
42 / 100
 1000 ms 138288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int K = 1 << 20; // check
const double pi = acos(-1);

typedef complex<double> comp;
typedef vector<comp> poly_C;
typedef vector<int64_t> poly;

comp w[K];

bool initialized = 0;
void init_fft() {
    if (initialized) {
        return;
    }
    initialized = 1;
    for (int i = 1; i < K; i *= 2) {
        for (int j = 0; j < i; j++) {
            w[i + j] = polar(1.0, pi * j / i);
        }
    }
}

template <typename T>
void fft(T* in, comp* out, int n, int k = 1) {
    if (n == 1) {
        *out = *in;
        return;
    }
    n /= 2;
    fft(in, out, n, 2 * k);
    fft(in + k, out + n, n, 2 * k);
    for (int i = 0; i < n; i++) {
        comp t = out[i + n] * w[i + n];
        out[i + n] = out[i] - t;
        out[i] += t;
    }
}

void align(poly& a, poly& b) {
    int n = a.size() + b.size() - 1;
    while (a.size() < n) a.push_back(0);
    while (b.size() < n) b.push_back(0);
}

poly_C eval(poly& a) {
    while (__builtin_popcount(a.size()) != 1) {
        a.push_back(0);
    }
    poly_C res(a.size());
    fft(a.data(), res.data(), a.size());
    return res;
}

poly inter(poly_C a) {
    int n = a.size();
    poly_C inv(n);
    fft(a.data(), inv.data(), n);
    poly res(n);
    for (int i = 0; i < n; i++) {
        res[i] = round(inv[i].real() / n);
    }
    reverse(res.begin() + 1, res.end());
    return res;
}

poly mult(poly a, poly b) {
    init_fft();
    align(a, b);
    poly_C A = eval(a);
    poly_C B = eval(b);
    for (int i = 0; i < A.size(); i++) {
        A[i] *= B[i];
    }
    return inter(A);
}

const ll inf = 1e18;
const int C = 10;
const int N = 1e5 + 10;
const int M = 1e6 + 1e5 + 10;

int cnt_suf[C][M];

int flag[N];
ll dp[(1 << C)][(1 << C)];

int flag_true[N + N];
int rig_true[C][N + N];

int b[N];
int lef[C][N], rig[C][N];
int pref[C][N], suf[C][N];

bool getbit(int mask, int bit) {
    return mask & (1 << bit);
}

ll mask_to_ll(int mask) {
    ll res = 0;
    for (int i = 1; i < C; i++) {
        if (getbit(mask, i)) {
            res = res * 10 + i;
            mask ^= (1 << i);
            break;
        }
    }
    for (int i = 0; i < C; i++) {
        if (getbit(mask, i)) {
            res = res * 10 + i;
        }
    }
    return res;
}

void init() {
    {
        for (int x = M - 1; x >= 1; x /= 10) {
            cnt_suf[x % 10][M - 1]++;
        }
    }
    for (int i = M - 2; i >= 1; i--) {
        int mask = 0;
        for (int x = i; x >= 1; x /= 10) {
            mask |= (1 << (x % 10));
        }
        for (int c = 0; c < C; c++) {
            if (getbit(mask, c)) {
                cnt_suf[c][i] = cnt_suf[c][i + 1] + 1;
            } else {
                cnt_suf[c][i] = 0;
            }
        }
    }

    flag[0] = (1 << 0);
    for (int i = 1; i <= N - 1; i++) {
        for (int j = i; j >= 1; j /= 10) {
            flag[i] |= (1 << (j % 10));
        }
        if (i <= 9'999) {
            flag[i] |= (1 << 0);
        }
    }

    flag_true[0] = (1 << 0);
    for (int i = 1; i <= 2 * N - 1; i++) {
        for (int j = i; j >= 1; j /= 10) {
            flag_true[i] |= (1 << (j % 10));
        }
    }

    for (int i = 0; i < (1 << C); i++) {
        for (int j = 0; j < (1 << C); j++) {
            dp[i][j] = inf;
        }
    }
    for (int mask = 0; mask < (1 << C); mask++) {
        for (int last = 0; last < C && last != 9; last++) {
            int pref_mask = mask | (1 << last);
            int suf_mask = mask | (1 << (last + 1));
            if (mask_to_ll(mask) != 0 || last != 0) {
                dp[pref_mask][suf_mask] = min(dp[pref_mask][suf_mask], mask_to_ll(mask == 1 ? 3 : mask) * 10 + last);
            }

            pref_mask = mask | (mask == 0 && last == 0 ? 0 : (1 << last)) | (1 << 9);
            suf_mask = mask | (1 << (last + 1)) | (1 << 0);
            dp[pref_mask][suf_mask] = min(dp[pref_mask][suf_mask], mask_to_ll(mask == 1 ? 3 : mask) * 100 + last * 10 + 9);
        }
    }
    for (int i = (1 << C) - 1; i >= 0; i--) {
        for (int j = (1 << C) - 1; j >= 0; j--) {
            for (int c = 0; c < C; c++) {
                dp[i][j] = min(dp[i][j], dp[i | (1 << c)][j]);
                dp[i][j] = min(dp[i][j], dp[i][j | (1 << c)]);
            }
        }
    }
}

void calc_lef_rig(int k) {
    const int n = 100'000;
    for (int c = 0; c < C; c++) {
        poly p(n, 0);
        poly q(k, 0);
        for (int i = 0; i < n; i++) {
            p[i] = getbit(flag[i], c);
        }
        for (int i = 1; i <= k; i++) {
            q[k - i] = b[i] == c;
        }
        auto r = mult(p, q);
        for (int i = 0; i < n; i++) {
            lef[c][i] = r[i];
            rig[c][i] = r[i + k - 1];
        }
    }
}

void calc_pref_suf(int k) {
    for (int c = 0; c < C; c++) {
        pref[c][0] = 0;
        suf[c][k + 1] = 0;
    }
    for (int i = 1; i <= k; i++) {
        for (int c = 0; c < C; c++) {
            pref[c][i] = pref[c][i - 1];
        }
        pref[b[i]][i]++;
    }
    for (int i = k; i >= 1; i--) {
        for (int c = 0; c < C; c++) {
            suf[c][i] = suf[c][i + 1];
        }
        suf[b[i]][i]++;
    }
}

void calc_rig_true(int k) {
    const int n = 200'000;
    for (int c = 0; c < C; c++) {
        poly p(n, 0);
        poly q(k, 0);
        for (int i = 0; i < n; i++) {
            p[i] = getbit(flag_true[i], c);
        }
        for (int i = 1; i <= k; i++) {
            q[k - i] = b[i] == c;
        }
        auto r = mult(p, q);
        for (int i = 0; i < n; i++) {
            rig_true[c][i] = r[i + k - 1];
        }
    }
}

ll solve_small(int k) {
    const int n = 100'000;
    for (int i = 1; i < n; i++) {
        bool ok = true;
        for (int c = 0; c < C; c++) {
            ok &= rig_true[c][i] == pref[c][k];
        }
        if (ok) {
            return i;
        }
    }
    return inf;
}

ll solve(int k) {
    calc_lef_rig(k);
    calc_rig_true(k);
    calc_pref_suf(k);

    const int n = 100'000;
    ll ans = inf;

    ans = min(ans, solve_small(k));

    for (int i = 0; i < n; i++) {
        if (i + k - 1 < n) {
            int need = 0;
            for (int c = 0; c < C; c++) {
                if (rig[c][i] != pref[c][k]) {
                    need |= (1 << c);
                }
            }
            ans = min(ans, dp[need][0] * n + i);
        } else {
            int len_pref = n - i;
            int len_suf = k - len_pref;
            int need_pref = 0, need_suf = 0;
            for (int c = 0; c < C; c++) {
                if (rig[c][i] != pref[c][len_pref]) {
                    need_pref |= (1 << c);
                }
                if (lef[c][len_suf - 1] != suf[c][k - len_suf + 1]) {
                    need_suf |= (1 << c);
                }
            }
            ans = min(ans, dp[need_pref][need_suf] * n + i);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    init();
    init_fft();

    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> b[i];
    }

    cout << solve(k) << "\n";

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

Compilation message

sequence.cpp: In function 'void align(poly&, poly&)':
sequence.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while (a.size() < n) a.push_back(0);
      |            ~~~~~~~~~^~~
sequence.cpp:48:21: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     while (b.size() < n) b.push_back(0);
      |            ~~~~~~~~~^~~
sequence.cpp: In function 'poly mult(poly, poly)':
sequence.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 114072 KB Output is correct
2 Correct 655 ms 114684 KB Output is correct
3 Correct 654 ms 114644 KB Output is correct
4 Correct 669 ms 113864 KB Output is correct
5 Correct 623 ms 114996 KB Output is correct
6 Correct 623 ms 114032 KB Output is correct
7 Correct 620 ms 114248 KB Output is correct
8 Correct 638 ms 115380 KB Output is correct
9 Correct 617 ms 112492 KB Output is correct
10 Correct 646 ms 114200 KB Output is correct
11 Correct 627 ms 113576 KB Output is correct
12 Correct 603 ms 115604 KB Output is correct
13 Correct 616 ms 114108 KB Output is correct
14 Correct 627 ms 114516 KB Output is correct
15 Correct 626 ms 114964 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 114936 KB Output is correct
2 Correct 615 ms 114520 KB Output is correct
3 Correct 628 ms 112948 KB Output is correct
4 Correct 640 ms 114256 KB Output is correct
5 Correct 626 ms 115228 KB Output is correct
6 Correct 629 ms 115288 KB Output is correct
7 Correct 619 ms 115276 KB Output is correct
8 Correct 622 ms 112864 KB Output is correct
9 Correct 631 ms 115428 KB Output is correct
10 Correct 625 ms 113556 KB Output is correct
11 Correct 630 ms 114384 KB Output is correct
12 Correct 626 ms 113944 KB Output is correct
13 Correct 612 ms 114008 KB Output is correct
14 Correct 631 ms 114832 KB Output is correct
15 Correct 632 ms 114424 KB Output is correct
16 Correct 617 ms 115564 KB Output is correct
17 Correct 637 ms 115008 KB Output is correct
18 Correct 630 ms 113852 KB Output is correct
19 Correct 616 ms 113972 KB Output is correct
20 Correct 626 ms 113540 KB Output is correct
21 Correct 622 ms 113624 KB Output is correct
22 Correct 630 ms 113856 KB Output is correct
23 Correct 631 ms 115396 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 112516 KB Output is correct
2 Correct 594 ms 115080 KB Output is correct
3 Correct 635 ms 114768 KB Output is correct
4 Correct 599 ms 115012 KB Output is correct
5 Correct 617 ms 115012 KB Output is correct
6 Correct 609 ms 113764 KB Output is correct
7 Execution timed out 1053 ms 138288 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 114532 KB Output is correct
2 Correct 626 ms 115072 KB Output is correct
3 Correct 629 ms 114996 KB Output is correct
4 Correct 642 ms 114020 KB Output is correct
5 Correct 805 ms 115180 KB Output is correct
6 Correct 625 ms 114876 KB Output is correct
7 Correct 623 ms 113792 KB Output is correct
8 Correct 624 ms 115400 KB Output is correct
9 Correct 641 ms 113704 KB Output is correct
10 Correct 628 ms 114696 KB Output is correct
11 Execution timed out 1061 ms 137464 KB Time limit exceeded
12 Halted 0 ms 0 KB -