Submission #834494

# Submission time Handle Problem Language Result Execution time Memory
834494 2023-08-22T14:56:37 Z shishankrawat93774 Palindrome-Free Numbers (BOI13_numbers) C++17
72.5 / 100
1 ms 340 KB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define fo(iter, start_value, less_than) for(int iter = start_value; iter<less_than; iter++)

#define noans cout<<"-1"
#define zero cout<<"0"
#define nline "\n"
#define space " "
#define MSBll(n) __lg(n)
#define vi vector<int> 
#define vpii vector<pair<int, int> > 
#define vvi vector<vector<int> > 
#define set_bits __builtin_popcountll
#define getunique(x) {sort(all(x)); x.erase(unique(all(x)), x.end());}
#define mem(x, val) memset(x, val, sizeof(x))

// const double PI = 3.1415926535897932384626433832795;
// const string pi = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";

const int mod = 1e9+7;
// const int mod = 998244353;
const ll INF = 1e18;
// const int N = 1e5+5;
// const int N = 2e5+5;
// const int N = 3e5+5;
// const int MX = INT_MAX;
// const int MN = INT_MIN;

#define int ll


mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int getRandomNumber(int l, int r){
   uniform_int_distribution<int> dist(l, r);
   return dist(rnd);
}


#define yes cout<<"YES"
#define no cout<<"NO"
//set MULTISET ka bhi dekh lena bhai

int dp[20][2][11][11];

int rec(int i, bool tight, int prv1, int prv2, const string &str, int n){
    if(i == n) return 1;

    int &ans = dp[i][tight][prv1+1][prv2+1];
    if(ans != -1) return ans;
    ans = 0;
    int ub = (tight?(str[i] - '0'):9);

    for(int dig = 0; dig <= ub; dig++){
        if(dig != prv1 and dig != prv2){
            ans += rec(i+1, (tight&(dig == ub)), dig, prv1, str, n);
        }
    }
    return ans;
}

signed main() {
// #ifndef ONLINE_JUDGE
//  freopen("Error.txt", "w", stderr);
// #endif
    fastio();

    int l, r; cin>>l>>r;

    string rstr = to_string(r);

    int lans = 0, rans = 0;
    memset(dp, -1, sizeof dp);
    rans = rec(0, 1, -1, -1, rstr, rstr.size());
    if(l){
        l--;
        memset(dp, -1, sizeof dp);
        string lstr = to_string(l);
        lans = rec(0, 1, -1, -1, lstr, lstr.size());
    }
    cout<<(rans - lans);

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