답안 #11144 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
11144	2014-11-15T01:03:47 Z	tncks0121	수열 (BOI14_sequence)	C++14	100 / 100	416 ms	3496 KB

sequence

//
//  main.cpp
//  BOI14_sequence
//
//  Created by 박수찬 on 14. 11. 14..
//  Copyright (c) 2014년 박수찬. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

typedef bitset<10> state;

ll solve (vector<state> a, bool chk) {
    ll ret = 123456789000000;
    
    // empty set
    bool is_empty = true;
    for(int i = 0; i < a.size(); i++) {
        if(a[i].count() != 0) is_empty = false;
    }
    if(is_empty) return !chk;
    
    
    if(a.size() == 1) {
        state t = a[0];
        if(t[0]) { // 0이 포함될 경우 : (smallest digit except 0) + 0 + (이후 digits)
            ret = 0;
            for(int i = 1; i <= 9; i++) if(t[i]){
                if(ret == 0) ret = i * 10;
                else ret = ret * 10 + i;
            }
        }else { // 그냥 순서대로
            ret = 0;
            for(int i = 1; i <= 9; i++) if(t[i]) ret = ret * 10 + i;
        }
        if(ret == 0) ret = 10;
    }else {
        for(int d = 0; d <= 9; d++) {
            // last digit is d
            vector<state> b;
            int x = d, i = 0;
            while(i < a.size()) {
                state n;
                for(; x <= 9 && i < a.size(); x++, i++) {
                    state t = a[i];
                    if(t[x]) t[x] = false;
                    n |= t;
                }
                x = 0;
                b.push_back(n);
            }
            
            if(a == b) continue;
            
            ll cand = solve(b, chk | !!d) * 10 + d;
            // 무조건 성립하는 건 아닌 거 같은데 ㅁㄴㅇㄹ
            if(cand == 0) {
                // N이 자연수여야 함. 따라서 현재까지 N도 0인데 윗digit들도 다 0이면 곤란함
                if(!chk) cand = 123456789000000;
                
                // 윗digit들이 다 0인데, 아랫digit들에 0이 하나도 없고 위에서 0을 요구하는 상황에서 cand=0이면 안 되구나 ㅠㅠ
                if(a[0][0]) cand = 123456789000000;
            }
            ret = min(ret, cand);
        }
    }
    return ret;
}

int main() {
    int K; scanf("%d", &K);
    vector<state> in(K);
    for(int i = 0; i < K; i++) {
        int x; scanf("%d", &x);
        in[i].set(x);
    }
    
    printf("%lld\n", solve(in, false));
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1676 KB	Output is correct
2	Correct	40 ms	1848 KB	Output is correct
3	Correct	40 ms	1848 KB	Output is correct
4	Correct	40 ms	1848 KB	Output is correct
5	Correct	36 ms	1848 KB	Output is correct
6	Correct	20 ms	1804 KB	Output is correct
7	Correct	188 ms	2896 KB	Output is correct
8	Correct	176 ms	2388 KB	Output is correct
9	Correct	224 ms	3496 KB	Output is correct
10	Correct	228 ms	3496 KB	Output is correct

Subtask #4
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1676 KB	Output is correct
2	Correct	0 ms	1676 KB	Output is correct
3	Correct	0 ms	1676 KB	Output is correct
4	Correct	0 ms	1676 KB	Output is correct
5	Correct	180 ms	2356 KB	Output is correct
6	Correct	0 ms	1676 KB	Output is correct
7	Correct	0 ms	1676 KB	Output is correct
8	Correct	0 ms	1676 KB	Output is correct
9	Correct	0 ms	1676 KB	Output is correct
10	Correct	0 ms	1676 KB	Output is correct
11	Correct	228 ms	3496 KB	Output is correct
12	Correct	380 ms	3496 KB	Output is correct
13	Correct	0 ms	1676 KB	Output is correct
14	Correct	4 ms	1676 KB	Output is correct
15	Correct	4 ms	1676 KB	Output is correct
16	Correct	4 ms	1676 KB	Output is correct
17	Correct	0 ms	1676 KB	Output is correct
18	Correct	0 ms	1676 KB	Output is correct
19	Correct	4 ms	1676 KB	Output is correct
20	Correct	4 ms	1676 KB	Output is correct
21	Correct	0 ms	1676 KB	Output is correct
22	Correct	0 ms	1676 KB	Output is correct
23	Correct	4 ms	1676 KB	Output is correct
24	Correct	0 ms	1676 KB	Output is correct
25	Correct	4 ms	1676 KB	Output is correct
26	Correct	4 ms	1676 KB	Output is correct
27	Correct	36 ms	1848 KB	Output is correct
28	Correct	36 ms	1848 KB	Output is correct
29	Correct	40 ms	1848 KB	Output is correct
30	Correct	40 ms	1848 KB	Output is correct
31	Correct	16 ms	1804 KB	Output is correct
32	Correct	164 ms	2896 KB	Output is correct
33	Correct	184 ms	2388 KB	Output is correct
34	Correct	244 ms	3496 KB	Output is correct
35	Correct	256 ms	3496 KB	Output is correct
36	Correct	308 ms	2932 KB	Output is correct
37	Correct	416 ms	3456 KB	Output is correct
38	Correct	232 ms	2564 KB	Output is correct
39	Correct	416 ms	3496 KB	Output is correct
40	Correct	400 ms	3496 KB	Output is correct

답안 #11144

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