oj.uz

Submission #11187

# Submission time Handle Problem Language Result Execution time Memory
11187 2014-11-18T14:16:38 Z qja0950 Sequence (BOI14_sequence) C++
25 / 100
 124 ms 3948 KB 
//
//  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 = 100000;
    if(the_min < n/10 + 1)
        the_min = n/10 + 1;
    next = new int [the_min];
    
    ll ans = (ll)(0x7fffffff) * (ll)(0x7fffffff);
    for(int i=0; i<10; i++) {
        int nextn = 0;
        
        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);
            first = (first | now);
        }
        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);
                first = (first | now);
            }
            next[nextn++] = first;
        }
    if(pp==0) {
//        printf("%d %d\n", i, nextn);
    }
        ll get = Get(next, nextn, pp+1);
        ll nowi = get * 10 + i;
        if(get == 0 && i == 0)
            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
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3948 KB Output is correct
2 Incorrect 100 ms 3948 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 3948 KB Output is correct
2 Incorrect 100 ms 3948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1600 KB Output is correct
2 Correct 52 ms 3948 KB Output is correct
3 Correct 40 ms 3948 KB Output is correct
4 Correct 56 ms 3948 KB Output is correct
5 Correct 60 ms 3948 KB Output is correct
6 Correct 28 ms 3948 KB Output is correct
7 Correct 76 ms 3948 KB Output is correct
8 Correct 72 ms 3948 KB Output is correct
9 Correct 124 ms 3948 KB Output is correct
10 Correct 84 ms 3948 KB Output is correct

Subtask #4
0.0 / 33.0

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