oj.uz

Submission #258194

# Submission time Handle Problem Language Result Execution time Memory
258194 2020-08-05T14:07:30 Z cheeheng Lucky Numbers (RMI19_lucky) C++14
28 / 100
 200 ms 1144 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9+7;

char S[100005];
int X[100005];
long long memo[10005][2][2];
long long dp2[100005][2];

int N, Q;
int K;

long long dp(int i, bool prev_digit_is_1, bool same_so_far){
    if(i == K){
        return 1;
    }else if(memo[i][prev_digit_is_1][same_so_far] != -1){
        return memo[i][prev_digit_is_1][same_so_far];
    }else if(!same_so_far){
        //return dp2[K-i][1]+dp2[K-i][0];

        if(prev_digit_is_1){
            return dp2[K-i][0];
        }else{
            return dp2[K-i][1] + dp2[K-i][0];
        }

        long long ans = 0;
        for(int j = 0; j < 10; j ++){
            if(prev_digit_is_1 && j == 3){
                continue;
            }

            ans += dp(i+1, j == 1, false);
        }
        ans %= MOD;

        //printf("memo[%d][%d][%d]=%lld\n", i, prev_digit_is_1, same_so_far, ans);
        return memo[i][prev_digit_is_1][same_so_far] = ans;
    }else{
        long long ans = 0;
        for(int j = 0; j < 10; j ++){
            if(j > X[i]){break;}
            if(prev_digit_is_1 && j == 3){
                continue;
            }

            ans += dp(i+1, j == 1, X[i] == j);
        }
        ans %= MOD;

        //printf("memo[%d][%d][%d]=%lld\n", i, prev_digit_is_1, same_so_far, ans);
        return memo[i][prev_digit_is_1][same_so_far] = ans;
    }
}

int main(){
    scanf("%d%d", &N, &Q);
    scanf(" %s", S);

    for(int i = 0; i < N; i ++){
        X[i] = S[i]-'0';
    }

    dp2[0][0] = 1;
    dp2[0][1] = 0;
    for(int i = 1; i <= N; i ++){
        dp2[i][0] = (dp2[i-1][1]*8 + dp2[i-1][0]*9)%MOD;
        dp2[i][1] = (dp2[i-1][1] + dp2[i-1][0])%MOD;
        //printf("dp2[%d][%d]=%lld\n", i, 0, dp2[i][0]);
        //printf("dp2[%d][%d]=%lld\n", i, 1, dp2[i][1]);
    }

    K = N;
    memset(memo, -1, sizeof(memo));
    printf("%lld\n", dp(0, false, true));

    for(int i = 0; i < Q; i ++){
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);

        if(t == 2){
            S[l-1] = r+'0';
        }else{
            l --;
            r --;
            for(int j = 0; j < r-l+1; j ++){
                X[j] = S[l+j]-'0';
            }
            K = r-l+1;
            memset(memo, -1, sizeof(memo));
            printf("%lld\n", dp(0, false, true));
        }
    }

    return 0;
}

Compilation message

lucky.cpp: In function 'int main()':
lucky.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
lucky.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", S);
     ~~~~~^~~~~~~~~~
lucky.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 888 KB Output is correct
2 Execution timed out 209 ms 1144 KB Time limit exceeded

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 888 KB Output is correct
2 Execution timed out 209 ms 1144 KB Time limit exceeded

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 143 ms 888 KB Output is correct
8 Execution timed out 209 ms 1144 KB Time limit exceeded

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 143 ms 888 KB Output is correct
8 Execution timed out 209 ms 1144 KB Time limit exceeded