oj.uz

Submission #302888

# Submission time Handle Problem Language Result Execution time Memory
302888 2020-09-19T11:34:34 Z 2fat2code Lucky Numbers (RMI19_lucky) C++17
0 / 100
 180 ms 13688 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
//#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int mod = 1e9 + 7;
const int nmax = 100005;

int n,q,dp[nmax][10],ans;
string s;

void add(int &a,int b){
    a = (a + b) % mod;
}

void calc(int digitleft,int pos,int prevdigit){
    cout << "CHECK " << prevdigit << '\n';
    for(int t=0;t<(int)(s[pos] - '0');t++){
        if(prevdigit == 1 && t == 3) continue;
        add(ans,dp[digitleft][t]);
    }
    if((int)(s[pos] - '0') == 3 && prevdigit == 1){
        return;
    }
    else if(digitleft == 1){
        add(ans,1LL);
        return;
    }
    else{
        calc(digitleft - 1, pos + 1, (int)(s[pos] - '0'));
    }
}

void precalc(){
    for(int i=0;i<=9;i++) dp[1][i] = 1;
    for(int i=2;i<=100000;i++){
        for(int j=0;j<=9;j++){
            for(int t=0;t<=9;t++){
                if(j == 1 && t == 3) continue;
                else{
                    add(dp[i][j],dp[i-1][t]);
                }
            }
        }
    }
}

int32_t main(){
  //  ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n >> q >> s;
    precalc();
    ans = 0;
    calc(n,0,-1);
    cout << ans << '\n';
    for(int i=1;i<=q;i++){
        int type;
        cin >> type;
        if(type == 1){
            int l,r;
            cin >> l >> r;
            --l;
            --r;
            ans = 0;
            calc(r-l+1,l,-1);
            cout << ans << '\n';
        }
        else{
            int l;
            char r;
            cin >> l >> r;
            s[l - 1] = r;
        }
    }
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 27.0

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