oj.uz

Submission #118682

# Submission time Handle Problem Language Result Execution time Memory
118682 2019-06-19T11:10:30 Z songc Sequence (BOI14_sequence) C++14
25 / 100
 261 ms 1472 KB 
#include <bits/stdc++.h>
#define INF 1234567890123456ll
using namespace std;
typedef long long LL;

int N, ans=1;
int A[20][101010];

LL f(int lv, int k){
    LL ans = INF;
    bool tf=true;
    for (int i=1; i<=k; i++) if (A[lv][i]) tf = false;
    if (tf) return 0;
    if (lv>15) return INF;

    if (k == 1){
        ans = 0;
        for (int i=1; i<10; i++) if (A[lv][1] & (1<<i)){
            ans = ans*10 + i;
            if (A[lv][1] & 1) ans *= 10, A[lv][1] ^= 1;
        }
        if (A[lv][1] & 1) ans = 10;
        return ans;
    }

    for (int i=0; i<10; i++){
        for (int j=1; j<=k; j++) A[lv+1][j] = 0;
        for (int j=1; j<=k; j++) A[lv+1][(i+j-1)/10+1] |= A[lv][j] & ~(1<<((i+j-1)%10));
        LL ret = f(lv+1, (i+k-1)/10+1);
        if (ret == INF) continue;
        if (ret == 0 && i == 0) ans = min(ans, 10ll);
        else ans = min(ans, ret*10+i);
    }
    return ans;
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++) {
        scanf("%d", &A[0][i]);
        A[0][i] = 1 << A[0][i];
    }
    printf("%lld\n", f(0, N));
    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
sequence.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[0][i]);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 3 ms 384 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 2 ms 256 KB Output is correct
2 Correct 33 ms 512 KB Output is correct
3 Correct 31 ms 512 KB Output is correct
4 Correct 30 ms 512 KB Output is correct
5 Correct 32 ms 512 KB Output is correct
6 Correct 24 ms 544 KB Output is correct
7 Correct 191 ms 1152 KB Output is correct
8 Correct 121 ms 768 KB Output is correct
9 Correct 261 ms 1472 KB Output is correct
10 Correct 247 ms 1408 KB Output is correct

Subtask #4
0 / 33.0

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