oj.uz

Submission #238056

# Submission time Handle Problem Language Result Execution time Memory
238056 2020-06-09T20:38:22 Z Sorting Lucky Numbers (RMI19_lucky) C++14
100 / 100
 153 ms 25976 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_Mod = 1e9 + 7;
const int k_N = 1e5 + 7;

int n, q;
string x;

pair<int, bool> dp[k_N][10][2];

int solve(int digits_left, int previous_digit, bool equal, int end){
    if(digits_left == 0)
        return 1;

    auto &[answer, solved] = dp[digits_left][previous_digit][equal];
    if(solved && !equal)
        return answer;

    solved = true;
    answer = 0;

    int max_digit = 9;
    if(equal){
        int position = end - digits_left + 1;
        max_digit = x[position] - '0';
    }

    for(int digit = 0; digit <= max_digit; ++digit){
        if(previous_digit == 1 && digit == 3)
            continue;
        bool new_equal = equal ? (digit == max_digit) : false;

        answer += solve(digits_left - 1, digit, new_equal, end);
        answer = (answer >= k_Mod) ? (answer - k_Mod) : answer;
    }

    return answer;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    cin >> x;

    cout << solve(n, 0, true, n - 1) << "\n";

    for(int i = 0; i < q; ++i){
        int t;
        cin >> t;

        if(t == 1){
            int l, r;
            cin >> l >> r;
            --l, --r;

            cout << solve(r - l + 1, 0, true,  r) << "\n";
        }
        else{
            int position;
            char value;
            cin >> position >> value;
            --position;

            x[position] = value;
        }
    }
}

Compilation message

lucky.cpp: In function 'int solve(int, int, bool, int)':
lucky.cpp:17:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto &[answer, solved] = dp[digits_left][previous_digit][equal];
           ^

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2580 KB Output is correct
2 Correct 71 ms 3104 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2580 KB Output is correct
2 Correct 71 ms 3104 KB Output is correct
3 Correct 126 ms 20836 KB Output is correct
4 Correct 128 ms 20856 KB Output is correct
5 Correct 139 ms 23416 KB Output is correct
6 Correct 153 ms 25976 KB Output is correct
7 Correct 151 ms 25976 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 46 ms 2580 KB Output is correct
8 Correct 71 ms 3104 KB Output is correct
9 Correct 28 ms 2528 KB Output is correct
10 Correct 42 ms 3072 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 46 ms 2580 KB Output is correct
8 Correct 71 ms 3104 KB Output is correct
9 Correct 126 ms 20836 KB Output is correct
10 Correct 128 ms 20856 KB Output is correct
11 Correct 139 ms 23416 KB Output is correct
12 Correct 153 ms 25976 KB Output is correct
13 Correct 151 ms 25976 KB Output is correct
14 Correct 28 ms 2528 KB Output is correct
15 Correct 42 ms 3072 KB Output is correct
16 Correct 106 ms 20736 KB Output is correct
17 Correct 105 ms 20736 KB Output is correct
18 Correct 120 ms 23304 KB Output is correct
19 Correct 129 ms 25856 KB Output is correct
20 Correct 127 ms 25856 KB Output is correct