oj.uz

답안 #11140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
11140 2014-11-15T00:39:55 Z tncks0121 수열 (BOI14_sequence) C++14
0 / 100
 400 ms 3496 KB 
//
//  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 = 12345678900000;
    
    // 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;
            }
            if(ret == 0) ret = 1;
        }else { // 그냥 순서대로
            ret = 0;
            for(int i = 1; i <= 9; i++) if(t[i]) ret = ret * 10 + i;
        }
    }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 = 12345678900000;
                
                // 윗digit들이 다 0인데, 아랫digit들에 0이 하나도 없고 위에서 0을 요구하는 상황에서 cand=0이면 안 되구나 ㅠㅠ
                if(a[0][0]) cand = 12345678900000;
            }
            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
0.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 4 ms 1676 KB Output is correct
9 Incorrect 0 ms 1676 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.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 Incorrect 0 ms 1676 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Correct 4 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 4 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 236 ms 3496 KB Output is correct
12 Correct 400 ms 3496 KB Output is correct
13 Incorrect 0 ms 1676 KB Output isn't correct
14 Halted 0 ms 0 KB -