Submission #865636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
865636	2023-10-24T12:47:23 Z	azimanov	Sequence (BOI14_sequence)	C++17	42 / 100	336 ms	26524 KB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template<int mod>
class Modular {
public:
    int val;
    Modular() : val(0) {}
    Modular(int new_val) : val(new_val) {
    }
    friend Modular operator+(const Modular& a, const Modular& b) {
        if (a.val + b.val >= mod) return a.val + b.val - mod;
        else return a.val + b.val;
    }
    friend Modular operator-(const Modular& a, const Modular& b) {
        if (a.val - b.val < 0) return a.val - b.val + mod;
        else return a.val - b.val;
    }
    friend Modular operator*(const Modular& a, const Modular& b) {
        return 1ll * a.val * b.val % mod;
    }
    friend Modular binpow(Modular a, long long n) {
        Modular res = 1;
        for (; n; n >>= 1) {
            if (n & 1) res *= a;
            a *= a;
        }
        return res;
    }
    /* ALTERNATIVE INVERSE FUNCTION USING EXTENDED EUCLIDEAN ALGORITHM
    friend void gcd(int a, int b, Modular& x, Modular& y) {
        if (a == 0) {
            x = Modular(0);
            y = Modular(1);
            return;
        }
        Modular x1, y1;
        gcd(b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
    }
    friend Modular inv(const Modular& a) {
        Modular x, y;
        gcd(a.val, mod, x, y);
        return x;
    }
    */
    friend Modular inv(const Modular& a) {
        return binpow(a, mod - 2);
    }
    Modular operator/(const Modular& ot) const {
        return *this * inv(ot);
    }
    Modular& operator++() {
        if (val + 1 == mod) val = 0;
        else ++val;
        return *this;
    }
    Modular operator++(int) {
        Modular tmp = *this;
        ++(*this);
        return tmp;
    }
    Modular operator+() const {
        return *this;
    }
    Modular operator-() const {
        return 0 - *this;
    }
    Modular& operator+=(const Modular& ot) {
        return *this = *this + ot;
    }
    Modular& operator-=(const Modular& ot) {
        return *this = *this - ot;
    }
    Modular& operator*=(const Modular& ot) {
        return *this = *this * ot;
    }
    Modular& operator/=(const Modular& ot) {
        return *this = *this / ot;
    }
    bool operator==(const Modular& ot) const {
        return val == ot.val;
    }
    bool operator!=(const Modular& ot) const {
        return val != ot.val;
    }
    bool operator<(const Modular& ot) const {
        return val < ot.val;
    }
    bool operator>(const Modular& ot) const {
        return val > ot.val;
    }
    explicit operator int() const {
        return val;
    }
};

template <int mod>
Modular<mod> any_to_mint(ll a) {
    a %= mod;
    return a < 0 ? a + mod : a;
}

template<int mod>
istream& operator>>(istream& istr, Modular<mod>& x) {
    return istr >> x.val;
}

template<int mod>
ostream& operator<<(ostream& ostr, const Modular<mod>& x) {
    return ostr << x.val;
}

template <int mod = 998244353, int root = 3>
class NTT {
    using Mint = Modular<mod>;
public:
    static vector<int> mult(const vector<int>& a, const vector<int>& b) {
        vector<Mint> amod(a.size());
        vector<Mint> bmod(b.size());
        for (int i = 0; i < a.size(); i++) {
            amod[i] = any_to_mint<mod>(a[i]);
        }
        for (int i = 0; i < b.size(); i++) {
            bmod[i] = any_to_mint<mod>(b[i]);
        }
        vector<Mint> resmod = mult(amod, bmod);
        vector<int> res(resmod.size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = resmod[i].val;
        }
        return res;
    }
    static vector<Mint> mult(const vector<Mint>& a, const vector<Mint>& b) {
        int n = int(a.size()), m = int(b.size());
        if (!n || !m) return {};
        int lg = 0;
        while ((1 << lg) < n + m - 1) lg++;
        int z = 1 << lg;
        auto a2 = a, b2 = b;
        a2.resize(z);
        b2.resize(z);
        nft(false, a2);
        nft(false, b2);
        for (int i = 0; i < z; i++) a2[i] *= b2[i];
        nft(true, a2);
        a2.resize(n + m - 1);
        Mint iz = inv(Mint(z));
        for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
        return a2;
    }

private:
    static void nft(bool type, vector<Modular<mod>> &a) {
        int n = int(a.size()), s = 0;
        while ((1 << s) < n) s++;
        assert(1 << s == n);
        static vector<Mint> ep, iep;
        while (int(ep.size()) <= s) {
            ep.push_back(binpow(Mint(root), (mod - 1) / (1 << ep.size())));
            iep.push_back(inv(ep.back()));
        }
        vector<Mint> b(n);
        for (int i = 1; i <= s; i++) {
            int w = 1 << (s - i);
            Mint base = type ? iep[i] : ep[i], now = 1;
            for (int y = 0; y < n / 2; y += w) {
                for (int x = 0; x < w; x++) {
                    auto l = a[y << 1 | x];
                    auto r = now * a[y << 1 | x | w];
                    b[y | x] = l + r;
                    b[y | x | n >> 1] = l - r;
                }
                now *= base;
            }
            swap(a, b);
        }
    }
};

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

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

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;
}

int vec_to_mask(const vector<int>& vec) {
    int mask = 0;
    for (int i : vec) {
        mask |= (1 << i);
    }
    return mask;
}

void init() {
    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));
        }
    }
    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++) {
            if (mask == 0 && last == 0) {
                continue;
            }
            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 | (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++) {
        vector<int> p(n, 0);
        vector<int> 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 = NTT<998244353, 3>::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]++;
    }
}

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

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

    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);
                }
            }
            if (need == 0) {
                if (i == 0) {
                    ans = min(ans, ll(n));
                } else {
                    ans = min(ans, ll(i));
                }
            } else {
                if (need == 1) {
                    need = 3;
                }
                ll x = mask_to_ll(need);
                ans = min(ans, x * 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][len_suf]) {
                    need_suf |= (1 << c);
                }
            }
            if (dp[need_pref][need_suf] != inf) {
                ans = min(ans, dp[need_pref][need_suf] * n + i);
            }
        }
    }
    return ans;
}

ll slow(int k) {
    for (int n = 1; n <= 1000; n++) {
        bool ok = true;
        for (int i = 1; i <= k; i++) {
            ok &= getbit(flag[n + i - 1], b[i]);
        }
        if (ok) {
            return n;
        }
    }
    return -1;
}

void stress() {
    mt19937 rnd;
    while (true) {
        int k = rnd() % 10 + 1;
        for (int i = 1; i <= k; i++) {
            b[i] = rnd() % C;
        }
        ll res = slow(k);
        if (res == -1) {
            continue;
        }
        ll ans = solve(k);
        if (ans == res) {
            cout << "OK" << endl;
        } else {
            cout << "WA\n";
            cout << k << "\n";
            for (int i = 1; i <= k; i++) {
                cout << b[i] << " ";
            }
            cout << "\n\n";
            cout << ans << " " << res << "\n";
            break;
        }
    }
    exit(0);
}

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

    init();

    // stress();

    // cout << dp[vec_to_mask({1, 2, 3})][vec_to_mask({9, 0, 1, 4})] << "\n";

    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> b[i];
    }
//    k = 100'000;
//    for (int i = 1; i <= k; i++) {
//        b[i] = 0;
//    }
    cout << solve(k) << "\n";

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

Compilation message

sequence.cpp: In instantiation of 'static std::vector<int> NTT<mod, root>::mult(const std::vector<int>&, const std::vector<int>&) [with int mod = 998244353; int root = 3]':
sequence.cpp:274:46:   required from here
sequence.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
sequence.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for (int i = 0; i < b.size(); i++) {
      |                         ~~^~~~~~~~~~
sequence.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int i = 0; i < res.size(); i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	26524 KB	Output is correct
2	Correct	173 ms	26028 KB	Output is correct
3	Correct	176 ms	26012 KB	Output is correct
4	Correct	172 ms	26076 KB	Output is correct
5	Correct	174 ms	25964 KB	Output is correct
6	Correct	175 ms	26040 KB	Output is correct
7	Correct	173 ms	26004 KB	Output is correct
8	Correct	180 ms	26312 KB	Output is correct
9	Correct	175 ms	26204 KB	Output is correct
10	Correct	174 ms	26064 KB	Output is correct
11	Correct	173 ms	26220 KB	Output is correct
12	Correct	179 ms	26016 KB	Output is correct
13	Correct	174 ms	26020 KB	Output is correct
14	Correct	173 ms	25992 KB	Output is correct
15	Correct	175 ms	26020 KB	Output is correct

Subtask #2

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	26008 KB	Output is correct
2	Correct	175 ms	26024 KB	Output is correct
3	Correct	183 ms	26240 KB	Output is correct
4	Correct	173 ms	26004 KB	Output is correct
5	Correct	173 ms	26048 KB	Output is correct
6	Correct	177 ms	25988 KB	Output is correct
7	Correct	174 ms	26220 KB	Output is correct
8	Correct	174 ms	26080 KB	Output is correct
9	Correct	173 ms	26220 KB	Output is correct
10	Correct	187 ms	26200 KB	Output is correct
11	Correct	175 ms	26060 KB	Output is correct
12	Correct	177 ms	26152 KB	Output is correct
13	Correct	178 ms	26308 KB	Output is correct
14	Correct	173 ms	26088 KB	Output is correct
15	Correct	173 ms	26020 KB	Output is correct
16	Correct	173 ms	26376 KB	Output is correct
17	Correct	174 ms	26080 KB	Output is correct
18	Correct	176 ms	26000 KB	Output is correct
19	Correct	173 ms	26020 KB	Output is correct
20	Correct	173 ms	26116 KB	Output is correct
21	Correct	173 ms	26052 KB	Output is correct
22	Correct	176 ms	26132 KB	Output is correct
23	Correct	177 ms	26208 KB	Output is correct

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	177 ms	26076 KB	Output is correct
2	Correct	174 ms	26160 KB	Output is correct
3	Correct	180 ms	26512 KB	Output is correct
4	Incorrect	175 ms	26156 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	26176 KB	Output is correct
2	Correct	180 ms	26192 KB	Output is correct
3	Correct	174 ms	26052 KB	Output is correct
4	Correct	175 ms	26212 KB	Output is correct
5	Correct	326 ms	25640 KB	Output is correct
6	Correct	174 ms	26208 KB	Output is correct
7	Correct	177 ms	26012 KB	Output is correct
8	Correct	174 ms	26056 KB	Output is correct
9	Correct	174 ms	25996 KB	Output is correct
10	Correct	173 ms	26108 KB	Output is correct
11	Correct	332 ms	26124 KB	Output is correct
12	Correct	336 ms	25924 KB	Output is correct
13	Correct	173 ms	25992 KB	Output is correct
14	Correct	182 ms	26324 KB	Output is correct
15	Correct	174 ms	26032 KB	Output is correct
16	Correct	174 ms	26004 KB	Output is correct
17	Correct	174 ms	26032 KB	Output is correct
18	Correct	173 ms	26004 KB	Output is correct
19	Correct	173 ms	26056 KB	Output is correct
20	Correct	175 ms	26044 KB	Output is correct
21	Correct	180 ms	25972 KB	Output is correct
22	Correct	179 ms	26176 KB	Output is correct
23	Correct	175 ms	26064 KB	Output is correct
24	Correct	175 ms	26124 KB	Output is correct
25	Correct	174 ms	26220 KB	Output is correct
26	Correct	175 ms	26236 KB	Output is correct
27	Correct	174 ms	26196 KB	Output is correct
28	Correct	174 ms	26160 KB	Output is correct
29	Incorrect	175 ms	26308 KB	Output isn't correct
30	Halted	0 ms	0 KB	-