oj.uz

Submission #491911

# Submission time Handle Problem Language Result Execution time Memory
491911 2021-12-05T00:12:03 Z jeroenodb Sequence (BOI14_sequence) C++14
42 / 100
 749 ms 460 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;
                }
                tmp/=10;
            }
            if(!covered) cur.back().insert(b[j]);
        }
        ans = min(ans, solve(cur)*mxK+i);
    }
    cout << ans << '\n';
}

Subtask #1
9.0 / 9.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 Correct 0 ms 204 KB Output is correct
8 Correct 13 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 59 ms 204 KB Output is correct
15 Correct 52 ms 204 KB Output is correct

Subtask #2
33.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 Correct 14 ms 288 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 13 ms 296 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 32 ms 204 KB Output is correct
12 Correct 0 ms 288 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 52 ms 204 KB Output is correct
17 Correct 52 ms 204 KB Output is correct
18 Correct 7 ms 296 KB Output is correct
19 Correct 16 ms 204 KB Output is correct
20 Correct 51 ms 276 KB Output is correct
21 Correct 15 ms 292 KB Output is correct
22 Correct 58 ms 324 KB Output is correct
23 Correct 55 ms 288 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 69 ms 332 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 0 ms 204 KB Output is correct
5 Incorrect 749 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -