Submission #11188

#	Time	Username	Problem	Language	Result	Execution time	Memory
11188		qja0950	Sequence (BOI14_sequence)	C++98	100 / 100	148 ms	3972 KiB

sequence

//
//  main.cpp
//  32
//
//  Created by KJBS2 on 2014. 11. 18..
//  Copyright (c) 2014년 KJBS2. All rights reserved.
//

#include <stdio.h>

#define MAXN 101101
typedef long long ll;

int N;
int Nr[MAXN];

void INPUT() {
    scanf("%d", &N);
    for(int i=0; i<N; i++) {
        int x; scanf("%d", &x);
        Nr[i] = (1 << x);
    }
    return;
}
ll Get(int Now[], int n, int pp) {
    if(n==1) {
        ll ans = 0;
        
        bool iszero = false;
            if( (Now[0] >> 0) % 2 == 1 )
                iszero = true;
        if(!iszero) {
            for(int i=1; i<10; i++) {
                if( (Now[0] >> i) % 2 == 1 ) {
                    ans *= 10;
                    ans += i;
                }
            }
            return ans;
        }else{
            int p = -1;
            for(int i=1; i<10; i++)
                if( (Now[0] >> i) % 2 == 1 ) {
                    p = i;
                    break;
                }
            if(p == -1) return 10;
            ans = p * 10;
            
            for(int i=p+1; i<10; i++) {
                if( (Now[0] >> i) % 2 == 1 ) {
                    ans *= 10;
                    ans += i;
                }
            }
        }
    }
    if(pp>5) {
        ll ans = 0;
        
        bool iszero = false;
            for(int j=0; j<n; j++)
                if( (Now[j] >> 0) % 2 == 1 )
                    iszero = true;
        if(!iszero) {
            for(int i=1; i<10; i++) {
                for(int j=0; j<n; j++) {
                    if( (Now[j] >> i) % 2 == 1 ) {
                        ans *= 10;
                        ans += i;
                    }
                }
            }
            return ans;
        }else{
            int p = -1;
            for(int i=1; i<10; i++) {
                for(int j=0; j<n; j++)
                    if( (Now[j] >> i) % 2 == 1 ) {
                        p = i;
                        break;
                    }
                if(p != -1) break;
            }
            if(p == -1) return 10;
            ans = p * 10;
            
            for(int i=p+1; i<10; i++) {
                for(int j=0; j<n; j++) {
                    if( (Now[j] >> i) % 2 == 1 ) {
                        ans *= 10;
                        ans += i;
                    }
                }
            }
        }
        return ans;
    }
    int *next;
    
    int the_min = MAXN;
    next = new int [the_min];
    
    ll ans = (ll)(0x7fffffff) * (ll)(0x7fffffff);
    for(int i=0; i<10; i++) {
        int nextn = 0;
        
        bool empty = true;
        bool zz = true;
        
        int first = 0;
        for(int j=0; j<10-i && j<n; j++) {
            int p = i+j;
            int now = Now[j];
            if( (Now[j] >> p) % 2 == 1 ) {
                now -= (1 << p);
                if(p == 0) zz = false;
            }
            first = (first | now);
        }
        if(first != 0) empty = false;
        next[nextn++] = first;
        
        int t = 10-i;
        
        for(int j=t; j<n; j+=10) {
            int first = 0;
            for(int k=0; k<10 && j+k<n; k++) {
                int now = Now[j+k];
                if( (Now[j+k] >> k) % 2 == 1 ) {
                    now -= (1 << k);
                    if(k == 0) zz = false;
                }
                first = (first | now);
            }
            if(first != 0) empty = false;
            next[nextn++] = first;
        }
    if(pp==0) {
//        printf("%d %d\n", i, nextn);
    }
        ll get = 0;
        if(empty == false)
            get = Get(next, nextn, pp+1);
        ll nowi = get * 10 + i;
        if(get == 0 && i == 0 && zz == false) {
            nowi = 10;
        }
        
            if(ans > nowi)
                ans = nowi;
        if(pp==0) {
//            printf(">%d %lld\n", i, nowi);
        }
    }
    delete [] next;
    
    return ans;
}
int main() {
    INPUT();
    printf("%lld", Get(Nr, N, 0) );
}

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33