Submission #1109456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109456		Kirill22	Sequence (BOI14_sequence)	C++17	100 / 100	183 ms	2044 KiB

sequence

#include "bits/stdc++.h"
 
using namespace std;
 
bool contain(long long x, int c) {
    while (x > 0) {
        if (x % 10 == c) {
            return true;
        }
        x /= 10;
    }
    return false;
}
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[i] += (1 << x);
        b[i] = x;
    }
    long long ans = (long long) 1e18;
    auto check = [&] (long long x) {
        if (x >= ans) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            if (!contain(x + i, b[i])) {
                return false;
            }
        }
        return true;
    };
    auto dfs = [&] (auto&& dfs, string tmp, vector<int> a) -> void {
        if ((int) tmp.size() >= 6 && (int) a.size() > 1) {
            return;
        }
        if ((int) a.size() == 1) {
            if (!a[0]) {
                std::reverse(tmp.begin(), tmp.end());
                long long res = stoll(tmp);
                if (res && check(res)) {
                    ans = res;
                }
                if (!tmp.empty() && tmp[0] == '0') {
                    std::reverse(tmp.begin(), tmp.end());
                    tmp.push_back('1');
                    std::reverse(tmp.begin(), tmp.end());
                    res = stoll(tmp);
                }
                if (res && check(res)) {
                    ans = res;
                }
                return;
            }
            string s = tmp;
            if (a[0] == 1) {
                a[0] = 3;
            }
            for (int i = 9; i > 0; i--) {
                if (a[0] >> i & 1) {
                    s.push_back((char) '0' + i);
                }
            }
            if (a[0] % 2) {
                char c = s.back();
                s.back() = '0';
                s.push_back(c);
            }
            std::reverse(s.begin(), s.end());
            long long res = stoll(s);
            if (res && check(res)) {
                ans = res;
            }
            return;
        }
        for (int x = 0; x < 10; x++) {
            vector<int> b = {0};
            int y = x;
            for (int i = 0; i < (int) a.size(); i++) {
                int msk = a[i];
                if (msk >> y & 1) {
                    msk -= (1 << y);
                }
                b.back() |= msk;
                y = (y + 1) % 10;
                if (y == 0 && i + 1 < (int) a.size()) {
                    b.push_back(0);
                }
            }
            string tmp2 = tmp;
            tmp2.push_back((char) '0' + x);
            dfs(dfs, tmp2, b);
        }
    };
    dfs(dfs, "", a);
    cout << ans << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33