답안 #98865 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98865	2019-02-26T20:24:55 Z	SpeedOfMagic	수열 (BOI14_sequence)	C++17	100 / 100	418 ms	2592 KB

sequence

/** 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(vint a, int start, int h = 0, bool lez = 1) {
    if (sz(a) == 1) {
        int p = 0;
        int lz = 0;
        rep(i, 0, 10)
            if (a[0] & (1 << i)) {
                if (i == 0)
                    lz = 1;
                else if ((1 << i) & a[0]) {
                    p = (p * 10) + i;
                    if (lz) {
                        p *= 10;
                        lz = 0;
                    }
                }
            }

        if (lz)
            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
            int r = 0;
            rep(j, 0, 9)
                if (((1 << j) & a[0]) && j != i)
                    r |= (1 << j);

            rep(j, 1, 10)
                if (((1 << j) & a[1]) && j != i + 1)
                    r |= (1 << j);
            solve({r}, pw[h + 1] * i + pw[h] * 9 + start, h + 2, i == 0 && a[0]);
        }
    }

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

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

        solve(b, y * pw[h] + start, h + 1, y == 0 && a[0]);
    }
}
void run() {
    int k;
    get k;
    vint a(k);
    rep(i, 0, k) {
        int d;
        get d;
        a[i] = (1 << 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	5 ms	356 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	284 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	6 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	5 ms	388 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct

Subtask #2
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	7 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	7 ms	384 KB	Output is correct
12	Correct	6 ms	384 KB	Output is correct
13	Correct	6 ms	512 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	4 ms	384 KB	Output is correct
16	Correct	6 ms	384 KB	Output is correct
17	Correct	8 ms	484 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	7 ms	384 KB	Output is correct
21	Correct	4 ms	384 KB	Output is correct
22	Correct	7 ms	512 KB	Output is correct
23	Correct	6 ms	384 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	39 ms	512 KB	Output is correct
3	Correct	45 ms	512 KB	Output is correct
4	Correct	38 ms	512 KB	Output is correct
5	Correct	42 ms	512 KB	Output is correct
6	Correct	26 ms	640 KB	Output is correct
7	Correct	238 ms	1636 KB	Output is correct
8	Correct	210 ms	1124 KB	Output is correct
9	Correct	315 ms	2296 KB	Output is correct
10	Correct	311 ms	2352 KB	Output is correct

Subtask #4
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	356 KB	Output is correct
5	Correct	181 ms	1180 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	8 ms	384 KB	Output is correct
11	Correct	354 ms	2540 KB	Output is correct
12	Correct	338 ms	2352 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	428 KB	Output is correct
16	Correct	4 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	9 ms	384 KB	Output is correct
20	Correct	6 ms	384 KB	Output is correct
21	Correct	3 ms	384 KB	Output is correct
22	Correct	5 ms	392 KB	Output is correct
23	Correct	6 ms	384 KB	Output is correct
24	Correct	4 ms	384 KB	Output is correct
25	Correct	5 ms	384 KB	Output is correct
26	Correct	5 ms	384 KB	Output is correct
27	Correct	40 ms	640 KB	Output is correct
28	Correct	63 ms	512 KB	Output is correct
29	Correct	52 ms	612 KB	Output is correct
30	Correct	45 ms	632 KB	Output is correct
31	Correct	30 ms	420 KB	Output is correct
32	Correct	261 ms	1744 KB	Output is correct
33	Correct	178 ms	1280 KB	Output is correct
34	Correct	300 ms	2396 KB	Output is correct
35	Correct	326 ms	2368 KB	Output is correct
36	Correct	317 ms	1824 KB	Output is correct
37	Correct	397 ms	2344 KB	Output is correct
38	Correct	223 ms	1500 KB	Output is correct
39	Correct	392 ms	2588 KB	Output is correct
40	Correct	418 ms	2592 KB	Output is correct

답안 #98865

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 33.0 / 33.0

Subtask #3 25.0 / 25.0

Subtask #4 33.0 / 33.0

Subtask #1
9.0 / 9.0

Subtask #2
33.0 / 33.0

Subtask #3
25.0 / 25.0

Subtask #4
33.0 / 33.0