oj.uz

Submission #238059

# Submission time Handle Problem Language Result Execution time Memory
238059 2020-06-09T20:54:10 Z Sorting Lucky Numbers (RMI19_lucky) C++14
28 / 100
 200 ms 2424 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, int> dp[k_N][10][2];
int iteration;

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 == iteration)
        return answer;

    solved = iteration;
    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;

    iteration = 1;
    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;

            ++iteration;
            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:18: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 4 ms 384 KB Output is correct
3 Correct 4 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 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 288 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 2424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 2424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 288 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Execution timed out 1093 ms 2424 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 288 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Execution timed out 1093 ms 2424 KB Time limit exceeded
8 Halted 0 ms 0 KB -