제출 #491911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491911		jeroenodb	수열 (BOI14_sequence)	C++14	42 / 100	749 ms	460 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
ll solve(vector<set<int>> cur, bool ninetrick=false) {
    if(all_of(all(cur), [&](const set<int>& s){return s.empty();})) 
        return 0;
    if(cur.size()==1) {
        ll ans=0;
        vi v(all(cur[0]));
        if(v[0]==0) {
            if(v.size()==1) v.push_back(1);
            swap(v[0],v[1]);
        }
        for(auto i : v) ans = ans*10+i;
        return ans;
    }
    // one digit gets made one higher
    ll ans = 1e18;
    for(int i=0;i<10;++i) {
        // brute force this least significant digit
        auto c = cur;
        c[0].erase(i); c[1].erase(i+1);
        vi v;
        set_union(all(c[0]),all(c[1]),back_inserter(v));
        auto cr = solve({set<int>{all(v)}})*10+i;
        if(cr==0) cr=10;
        ans = min(cr,ans);
    }
    
    if(!ninetrick) {
        cur[0].erase(9), cur[1].erase(0);
        ans = min(ans, solve(cur,true)*10 + 9);
    }
    return ans;

}
const int mxK=1000;
bool brute(const vi& b,int i) {
    for(auto& dig : b) {
        int at = i;
        bool bad=true;
        while(at) {
            if(at%10==dig) {
                bad=false;
                break;
            }
            at/=10;
        }
        if(bad) return false;
        i++;
    }
    return true;
}
int main() {
    int k; cin >> k;
    vi b(k);
    for(auto& i : b) cin >> i;
    // only 2**20 end states.
    ll ans = 1e18;
    for(int i=0;i<mxK;++i) {
        if(brute(b,i)) {
            cout << i << '\n';
            exit(0);
        }
    }
    for(int i=0;i<mxK;++i) {
        vector<set<int>> cur = {{}};
        for(int j=0;j<k;++j) {
            int tmp = i+j;
            if(tmp==mxK) cur.push_back({});
            tmp%=mxK;
            bool covered=false;
            for(int rep=0;rep<3;++rep) {
                if(tmp%10==b[j]) {
                    covered=true;
                    break;
                }
                tmp/=10;
            }
            if(!covered) cur.back().insert(b[j]);
        }
        ans = min(ans, solve(cur)*mxK+i);
    }
    cout << ans << '\n';
}

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