oj.uz

답안 #834553

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834553 2023-08-22T15:25:59 Z shishankrawat93774 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 2 ms 384 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][12][12];

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

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

    for(int dig = 0; dig <= ub; dig++){
        if(dig == 0){
            if(!s){
                ans += rec(i+1, (tight&(dig == ub)), prv1, prv2, 0, str, n);
            }else{
                if(dig != prv1 and dig != prv2){
                    ans += rec(i+1, (tight&(dig == ub)), dig, prv1, (s or dig), str, n);
                }
            }
        }else{
            if(dig != prv1 and dig != prv2){
                ans += rec(i+1, (tight&(dig == ub)), dig, prv1, (s or dig), 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);
    // rstr = "0000012";
    rans = rec(0, 1, -1, -2, 0, rstr, rstr.size());
    rans++;
    if(l){
        l--;
        memset(dp, -1, sizeof dp);
        string lstr = to_string(l);
        lans = rec(0, 1, -1, -2, 0, lstr, lstr.size());
        lans++;
    }
    cout<<(rans - lans);

    return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 1 ms 308 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 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 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 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 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 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 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 2 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 332 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 336 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 332 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 328 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 332 KB Output is correct