oj.uz

Submission #491908

# Submission time Handle Problem Language Result Execution time Memory
491908 2021-12-05T00:06:25 Z jeroenodb Sequence (BOI14_sequence) C++14
0 / 100
 779 ms 560 KB 
#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;
                }
            }
            if(!covered) cur.back().insert(b[j]);
        }
        ans = min(ans, solve(cur)*1000+i);
    }
    cout << ans << '\n';
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 14 ms 292 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 288 KB Output is correct
14 Incorrect 57 ms 204 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Incorrect 13 ms 292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 69 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 779 ms 560 KB Output isn't correct
6 Halted 0 ms 0 KB -