Submission #81016

#	Time	Username	Problem	Language	Result	Execution time	Memory
81016		SpeedOfMagic	Sequence (BOI14_sequence)	C++17	9 / 100	106 ms	11116 KiB

sequence

/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
template<typename T> using v = vector<T>;
//template<typename T, typename U>  using hmap = __gnu_pbds::gp_hash_table<T, U>;
#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const int N = 1000000;
vint d[10];
char dig[N][10];
bool correct(int a) {
    rep(i, 0, 10)
        for (int j : d[i]) {
            int k = a + j;
            bool h = 0;
            while (k) {
                if (k % 10 == i) {
                    h = 1;
                    break;
                }
                k /= 10;
            }
            if (!h)
                return 0;
        }
    return 1;
}
void run() {
    int k;
    get k;
    rep(i, 0, k) {
        int a;
        get a;
        d[a].pb(i);
    }
    
    memset(dig, 0, sizeof dig);
    rep(i, 1, N) {
        int j = i;
        while (j) {
            dig[i][j % 10] = 1;
            j /= 10;
        }
    }
    //print(dig[567892][9] == 1);
    
    int n = inf;
    rep(i, 1, N / 10) {
        bool z = 0;
        int pen = 0;
        rep(j, 0, 10) {
            for (int l : d[j]) {
                if (i + l >= N || !dig[i + l][j]) {
                    if (j == 0)
                        z = 1;
                    else {
                        pen = pen * 10 + j;
                        if (z) {
                            pen *= 10;
                            z = 0;
                        }
                    }
                    break;
                }
            }
        }
        if (z)
            pen = 10;
        n = min(n, pen * N + i);
    }
    put n;
    assert(correct(n));
}
int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed << setprecision(15); run(); return 0;}

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