oj.uz

Submission #11138

# Submission time Handle Problem Language Result Execution time Memory
11138 2014-11-14T23:21:18 Z tncks0121 Sequence (BOI14_sequence) C++14
0 / 100
 0 ms 1676 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;
            }
        }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) {
                // 답이 0이려면 b가 empty해야 할 듯.. 따라서
                // 자동 empty인가??
                if(!chk) cand = 12345678900000;
                
                // N이 자연수여야 하므로..
                for(int i = 0; i < a.size(); i++) {
                    if(a[i][i % 10]) 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Incorrect 0 ms 1676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Incorrect 0 ms 1676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Incorrect 0 ms 1676 KB Output isn't correct
3 Halted 0 ms 0 KB -