oj.uz

Submission #96142

# Submission time Handle Problem Language Result Execution time Memory
96142 2019-02-06T12:32:11 Z SpeedOfMagic Sequence (BOI14_sequence) C++17
0 / 100
 278 ms 22204 KB 
/** MIT License Copyright (c) 2018-2019(!) Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
template<typename T> using v = vector<T>;
//#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 fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
const long double EPS = 1e-9;
#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
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 starts here
const int M = 1000001;
char need[M][10];
int modsMin[10][7], modsMax[10][7];

void run() {
    rep(i, 0, M)
        rep(j, 0, 10)
            need[i][j] = 1;
    rep(d, 0, 10)
        rep(i, 0, 7) {
            modsMin[d][i] = 1000000000;
            modsMax[d][i] = -1;
        }

    int k;
    get k;
    rep(i, 0, k) {
        int d;
        get d;
        int cur = 10;
        rep(j, 0, 7) {
            modsMin[d][j] = min(modsMin[d][j], i % cur);
            modsMax[d][j] = max(modsMax[d][j], i % cur);
            cur *= 10;
        }
    }

    rep(d, 0, 10) {
        int cur = d;
        int tot = 10;
        rep(i, 0, 7) {
            if (modsMin[d][i] == 1000000000) {
                rep(j, 0, M)
                    need[j][d] = 0;
                break;
            }
            //modsMin[d][i] + x = 1000...0
            int l1 = (cur - modsMin[d][i] + tot) % tot, l2 = (cur - modsMax[d][i] + tot) % tot;
            int r1 = (l1 + tot / 10 - 1) % tot, r2 = (l2 + tot / 10 - 1) % tot;
            vint raw;
            for (int j = l1; j != r1; j = (j + 1) % tot)
                raw.pb(j);
            raw.pb(r1);
            vint pos;
            for (int j : raw)
                if ((l2 <= r2 && l2 <= j && j <= r2) || (l2 > r2 && (l2 <= j || j <= r2)))
                    pos.pb(j);

            int c = (d == 0) * tot;
            while (c < M) {
                for (int j : pos)
                    if (j + c < M)
                        need[j + c][d] = 0;
                c += tot;
            }

            tot *= 10;
            cur *= 10;
        }
    }

    long long ans = inf;
    rep(i, 1, 900001) {
        long long pans = i;
        long long num = 0;
        rep(j, 1, 10)
            if (need[i][j]) {
                num = num * 10 + j;
                if (need[i][0]) {
                    need[i][0] = 0;
                    num *= 10;
                }
            }
        if (need[i][0])
            num = 10;
        pans += num * 1000000;
        ans = min(ans, pans);
    }
    put ans;
}

signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); return 0;}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 22136 KB Output is correct
2 Incorrect 273 ms 22204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 22088 KB Output is correct
2 Incorrect 278 ms 22204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 20244 KB Output is correct
2 Incorrect 55 ms 20200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 22084 KB Output is correct
2 Incorrect 270 ms 22184 KB Output isn't correct
3 Halted 0 ms 0 KB -