Submission #11144

#	Time	Username	Problem	Language	Result	Execution time	Memory
11144		tncks0121	Sequence (BOI14_sequence)	C++14	100 / 100	416 ms	3496 KiB

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 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33