Submission #865627

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
865627	2023-10-24T12:35:31 Z	azimanov	Sequence (BOI14_sequence)	C++17	42 / 100	332 ms	26432 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++) {
            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) * 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) * 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:271: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	172 ms	25984 KB	Output is correct
2	Correct	172 ms	26092 KB	Output is correct
3	Correct	176 ms	26024 KB	Output is correct
4	Correct	172 ms	26212 KB	Output is correct
5	Correct	173 ms	25988 KB	Output is correct
6	Correct	177 ms	26220 KB	Output is correct
7	Correct	176 ms	26024 KB	Output is correct
8	Correct	172 ms	26040 KB	Output is correct
9	Correct	176 ms	26108 KB	Output is correct
10	Correct	174 ms	26036 KB	Output is correct
11	Correct	176 ms	26024 KB	Output is correct
12	Correct	173 ms	26212 KB	Output is correct
13	Correct	172 ms	26024 KB	Output is correct
14	Correct	173 ms	26020 KB	Output is correct
15	Correct	177 ms	26060 KB	Output is correct

Subtask #2

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	180 ms	26252 KB	Output is correct
2	Correct	173 ms	26208 KB	Output is correct
3	Correct	174 ms	26000 KB	Output is correct
4	Correct	173 ms	26108 KB	Output is correct
5	Correct	174 ms	25992 KB	Output is correct
6	Correct	174 ms	26224 KB	Output is correct
7	Correct	174 ms	26020 KB	Output is correct
8	Correct	177 ms	26020 KB	Output is correct
9	Correct	173 ms	26060 KB	Output is correct
10	Correct	172 ms	25984 KB	Output is correct
11	Correct	179 ms	26300 KB	Output is correct
12	Correct	175 ms	26232 KB	Output is correct
13	Correct	172 ms	26020 KB	Output is correct
14	Correct	179 ms	26316 KB	Output is correct
15	Correct	172 ms	26020 KB	Output is correct
16	Correct	172 ms	26048 KB	Output is correct
17	Correct	173 ms	25992 KB	Output is correct
18	Correct	173 ms	26020 KB	Output is correct
19	Correct	173 ms	26044 KB	Output is correct
20	Correct	177 ms	26148 KB	Output is correct
21	Correct	180 ms	25980 KB	Output is correct
22	Correct	173 ms	26040 KB	Output is correct
23	Correct	173 ms	26052 KB	Output is correct

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	177 ms	26432 KB	Output is correct
2	Correct	174 ms	26304 KB	Output is correct
3	Correct	176 ms	26360 KB	Output is correct
4	Incorrect	173 ms	26188 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	25984 KB	Output is correct
2	Correct	172 ms	26024 KB	Output is correct
3	Correct	175 ms	26168 KB	Output is correct
4	Correct	174 ms	26204 KB	Output is correct
5	Correct	321 ms	25708 KB	Output is correct
6	Correct	173 ms	25984 KB	Output is correct
7	Correct	174 ms	26152 KB	Output is correct
8	Correct	174 ms	26224 KB	Output is correct
9	Correct	174 ms	26020 KB	Output is correct
10	Correct	172 ms	26084 KB	Output is correct
11	Correct	327 ms	26124 KB	Output is correct
12	Correct	332 ms	26184 KB	Output is correct
13	Correct	173 ms	26224 KB	Output is correct
14	Correct	174 ms	26056 KB	Output is correct
15	Correct	179 ms	26404 KB	Output is correct
16	Correct	173 ms	26100 KB	Output is correct
17	Correct	172 ms	26176 KB	Output is correct
18	Correct	172 ms	26180 KB	Output is correct
19	Correct	176 ms	26000 KB	Output is correct
20	Correct	184 ms	25992 KB	Output is correct
21	Correct	189 ms	26204 KB	Output is correct
22	Correct	179 ms	26308 KB	Output is correct
23	Correct	175 ms	26068 KB	Output is correct
24	Correct	181 ms	26020 KB	Output is correct
25	Correct	178 ms	26056 KB	Output is correct
26	Correct	176 ms	26232 KB	Output is correct
27	Correct	189 ms	26416 KB	Output is correct
28	Correct	189 ms	26172 KB	Output is correct
29	Incorrect	189 ms	26380 KB	Output isn't correct
30	Halted	0 ms	0 KB	-