oj.uz

Submission #648838

# Submission time Handle Problem Language Result Execution time Memory
648838 2022-10-08T13:38:53 Z speedyArda Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 5 ms 1568 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
#define pb push_back
#define vll vector<long long>
#define vb vector<bool>
#define vi vector<int>
#define vs vector<string>
#define vpii vector< pair<int, int> >
#define pii pair<int, int>
#define pbb pair<bool, bool>
#define pll pair<long long, long long>
#define vvi vector< vector<int> > 
#define ld long double
#define mp make_pair
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

vi num;
ll dp[18][15][15][2][20]; // (pos) (last digit) (last  - 1 digit) (restricted) (digit count without beginning zeros)
ll a, b;

ll solve(int pos, int last, int beflast, int rest, int allzero)
{
    if(pos == num.size())
    {
       
        return 1;
    } 

    if(dp[pos][last][beflast][rest][allzero] != -1)
        return dp[pos][last][beflast][rest][allzero];
    
    ll res = 0;
    int limit;
    if(rest == 0)
        limit = num[pos];
    else
        limit = 9;
    for(int curr = 0; curr <= limit; curr++)
    {
        int newrest = rest;
        int newzero = allzero;
        if(rest == 0 && curr < limit)
            newrest = 1;
        if(allzero != 0)
            newzero++;
        else if(curr != 0)
            newzero = 1;
        if(newzero <= 1 || (newzero == 2 && last != curr)|| (last != curr && beflast != curr))
            res += solve(pos + 1, curr, last, newrest, newzero);
    }

    return dp[pos][last][beflast][rest][allzero] = res;
}

int main() 
{
    cin >> a >> b;
    memset(dp, -1, sizeof(dp));  
    a--;
    ll temp = a;
    while(temp > 0)
    {
        num.pb(temp % 10);
        temp /= 10;
    }  
    if(a == -1)
        num.pb(-1);    
    reverse(all(num));    
    ll left = solve(0, 0, 0, 0, 0);
    memset(dp, -1, sizeof(dp));
    temp = b;
    num.clear();
    while(temp > 0)
    {
        num.pb(temp % 10);
        temp /= 10;
    } 
    if(b == 0)
        num.pb(0);
    reverse(all(num));
    ll right = solve(0, 0, 0, 0, 0);
    cout << right - left << "\n";
}

Compilation message

numbers.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
numbers.cpp: In function 'll solve(int, int, int, int, int)':
numbers.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if(pos == num.size())
      |        ~~~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1452 KB Output is correct
3 Correct 3 ms 1568 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 2 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1492 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 3 ms 1492 KB Output is correct
20 Correct 2 ms 1492 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 3 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1552 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 5 ms 1492 KB Output is correct
17 Correct 3 ms 1492 KB Output is correct
18 Correct 3 ms 1492 KB Output is correct
19 Correct 3 ms 1492 KB Output is correct
20 Correct 3 ms 1492 KB Output is correct
21 Correct 3 ms 1492 KB Output is correct
22 Correct 2 ms 1492 KB Output is correct
23 Correct 3 ms 1492 KB Output is correct
24 Correct 3 ms 1492 KB Output is correct
25 Correct 3 ms 1492 KB Output is correct
26 Correct 5 ms 1492 KB Output is correct
27 Correct 3 ms 1492 KB Output is correct
28 Correct 3 ms 1492 KB Output is correct
29 Correct 3 ms 1492 KB Output is correct
30 Correct 3 ms 1492 KB Output is correct
31 Correct 3 ms 1492 KB Output is correct
32 Correct 4 ms 1492 KB Output is correct
33 Correct 3 ms 1492 KB Output is correct
34 Correct 3 ms 1492 KB Output is correct
35 Correct 3 ms 1492 KB Output is correct
36 Correct 3 ms 1492 KB Output is correct
37 Correct 3 ms 1568 KB Output is correct
38 Correct 3 ms 1456 KB Output is correct
39 Correct 3 ms 1492 KB Output is correct
40 Correct 3 ms 1492 KB Output is correct
41 Correct 3 ms 1492 KB Output is correct
42 Correct 3 ms 1568 KB Output is correct
43 Correct 3 ms 1492 KB Output is correct
44 Correct 3 ms 1568 KB Output is correct
45 Correct 3 ms 1568 KB Output is correct