oj.uz

Submission #98864

# Submission time Handle Problem Language Result Execution time Memory
98864 2019-02-26T20:15:22 Z SpeedOfMagic Sequence (BOI14_sequence) C++17
42 / 100
 1000 ms 12628 KB 
/** MIT License Copyright (c) 2018-2019 Vasilev 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-10;
#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
v<vint> pos;
int ans = inf;

bool has(v<char>& a, int d) { for (int i : a) if (i == d) return 1; return 0; }
int pw[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
void solve(v<v<char>> a, int start, int h = 0, bool lez = 1) {
    if (sz(a) == 1) {
        sort(a[0].begin(), a[0].end());
        int p = 0;
        int lz = 0;
        rep(i, 0, sz(a[0]))
            if (i == 0 || a[0][i] > a[0][i - 1]) {
                if (a[0][i] == 0)
                    lz++;
                else {
                    p = (p * 10) + a[0][i];
                    for (; lz; lz--)
                        p = (p * 10);
                }
            }

        if (lz) {
            p = 1;
            for (; lz; lz--)
                p = (p * 10);
        }

        if (p == 0 && lez)
            p = 1;
        p = p * pw[h] + start;
        ans = min(ans, p);
        return;
    } else if (sz(a) == 2) { //y = 9
        for (int i = 0; i < 9; i++) { //because 99 is useless
            v<char> r;
            for (int j : a[0])
                if (j != 9 && j != i)
                    r.pb(j);
            for (int j : a[1])
                if (j != 0 && j != i + 1)
                    r.pb(j);
            solve({r}, pw[h + 1] * i + pw[h] * 9 + start, h + 2, i == 0 && sz(a[0]));
        }
    }

    rep(y, 0, 10 - (sz(a) == 2)) {
        v<v<char>> b;
        b.pb(v<char>());
        int d = y;
        rep(i, 0, sz(a)) {
            for (int j = 0; j < 10; j++)
                if (j != d && has(a[i], j))
                    b.back().pb(j);

            d = (d + 1) % 10;
            if (d == 0 && i != sz(a) - 1)
                b.pb(v<char>());
        }

        solve(b, y * pw[h] + start, h + 1, y == 0 && sz(a[0]));
    }
}
void run() {
    int k;
    get k;
    v<v<char>> a(k);
    rep(i, 0, k) {
        int d;
        get d;
        a[i] = {(char) d};
    }

    solve(a, {});

    put ans;
}
/* 61
5
1 2 3 4 6
*//* 89
2
9 9
*//* 8
4
8 9 0 1
*//* 499
5
9 0 5 2 0
*//* 249
5
2 5 2 5 2
*//* 99
5
9 1 1 0 0
*/
signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); return 0;}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 12 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 13 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 44 ms 512 KB Output is correct
11 Correct 39 ms 580 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 44 ms 640 KB Output is correct
15 Correct 51 ms 508 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 13 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 20 ms 512 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 3 ms 388 KB Output is correct
11 Correct 23 ms 512 KB Output is correct
12 Correct 31 ms 384 KB Output is correct
13 Correct 34 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 43 ms 512 KB Output is correct
17 Correct 45 ms 504 KB Output is correct
18 Correct 8 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 38 ms 512 KB Output is correct
21 Correct 10 ms 384 KB Output is correct
22 Correct 42 ms 512 KB Output is correct
23 Correct 43 ms 512 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 120 ms 1744 KB Output is correct
3 Correct 123 ms 1876 KB Output is correct
4 Correct 132 ms 1872 KB Output is correct
5 Correct 135 ms 1788 KB Output is correct
6 Correct 91 ms 1280 KB Output is correct
7 Correct 894 ms 8944 KB Output is correct
8 Correct 554 ms 6148 KB Output is correct
9 Execution timed out 1076 ms 12628 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 12 ms 384 KB Output is correct
3 Correct 5 ms 356 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Execution timed out 1063 ms 5924 KB Time limit exceeded
6 Halted 0 ms 0 KB -