Submission #865609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
865609	2023-10-24T12:20:14 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));
            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();

    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 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:269: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	175 ms	25996 KB	Output is correct
2	Correct	175 ms	26020 KB	Output is correct
3	Correct	182 ms	26216 KB	Output is correct
4	Correct	180 ms	26084 KB	Output is correct
5	Correct	175 ms	26148 KB	Output is correct
6	Correct	183 ms	26080 KB	Output is correct
7	Correct	197 ms	26212 KB	Output is correct
8	Correct	178 ms	26120 KB	Output is correct
9	Correct	182 ms	25976 KB	Output is correct
10	Correct	174 ms	26128 KB	Output is correct
11	Correct	187 ms	26216 KB	Output is correct
12	Correct	191 ms	26024 KB	Output is correct
13	Correct	187 ms	26096 KB	Output is correct
14	Correct	174 ms	26028 KB	Output is correct
15	Correct	174 ms	26112 KB	Output is correct

Subtask #2

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	204 ms	26200 KB	Output is correct
2	Correct	183 ms	26016 KB	Output is correct
3	Correct	177 ms	26096 KB	Output is correct
4	Correct	185 ms	26124 KB	Output is correct
5	Correct	198 ms	26140 KB	Output is correct
6	Correct	187 ms	26060 KB	Output is correct
7	Correct	182 ms	26116 KB	Output is correct
8	Correct	181 ms	26004 KB	Output is correct
9	Correct	183 ms	26128 KB	Output is correct
10	Correct	176 ms	26204 KB	Output is correct
11	Correct	174 ms	26060 KB	Output is correct
12	Correct	176 ms	26128 KB	Output is correct
13	Correct	188 ms	26216 KB	Output is correct
14	Correct	179 ms	26008 KB	Output is correct
15	Correct	186 ms	26172 KB	Output is correct
16	Correct	177 ms	26056 KB	Output is correct
17	Correct	182 ms	26236 KB	Output is correct
18	Correct	175 ms	26024 KB	Output is correct
19	Correct	174 ms	26024 KB	Output is correct
20	Correct	183 ms	26368 KB	Output is correct
21	Correct	174 ms	26020 KB	Output is correct
22	Correct	173 ms	26228 KB	Output is correct
23	Correct	175 ms	26348 KB	Output is correct

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	25984 KB	Output is correct
2	Correct	175 ms	26156 KB	Output is correct
3	Correct	182 ms	26400 KB	Output is correct
4	Incorrect	174 ms	26380 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	26016 KB	Output is correct
2	Correct	177 ms	26336 KB	Output is correct
3	Correct	173 ms	26176 KB	Output is correct
4	Correct	173 ms	26000 KB	Output is correct
5	Correct	328 ms	25804 KB	Output is correct
6	Correct	175 ms	26164 KB	Output is correct
7	Correct	175 ms	25980 KB	Output is correct
8	Correct	174 ms	26084 KB	Output is correct
9	Correct	174 ms	26020 KB	Output is correct
10	Correct	173 ms	26056 KB	Output is correct
11	Correct	332 ms	26184 KB	Output is correct
12	Correct	326 ms	25928 KB	Output is correct
13	Correct	173 ms	25984 KB	Output is correct
14	Correct	173 ms	26060 KB	Output is correct
15	Correct	172 ms	26040 KB	Output is correct
16	Correct	172 ms	26020 KB	Output is correct
17	Correct	174 ms	26044 KB	Output is correct
18	Correct	174 ms	26092 KB	Output is correct
19	Correct	173 ms	26228 KB	Output is correct
20	Correct	173 ms	26132 KB	Output is correct
21	Correct	180 ms	26432 KB	Output is correct
22	Correct	174 ms	26024 KB	Output is correct
23	Correct	174 ms	26124 KB	Output is correct
24	Correct	174 ms	26048 KB	Output is correct
25	Correct	173 ms	26024 KB	Output is correct
26	Correct	173 ms	26100 KB	Output is correct
27	Correct	174 ms	26256 KB	Output is correct
28	Correct	173 ms	26388 KB	Output is correct
29	Incorrect	174 ms	26424 KB	Output isn't correct
30	Halted	0 ms	0 KB	-