oj.uz

Submission #575324

# Submission time Handle Problem Language Result Execution time Memory
575324 2022-06-10T08:11:22 Z ktkerem Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 444 KB 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
/*#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 vll;
typedef unsigned __int128 uvll;
ll _i=0;
#define ffn(x) _i=x
#define llll std::pair<ll , ll>
#define stitr set<ll>::iterator
#define fora(y,x) for(ll y=_i;x>y;y++)
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e9 + 7; 
const ll ous = 1e6 + 7;
const ll dx[4] = {1 , 0 , 0 , -1} , dy[4] = {0,1,-1,0};
std::string a , b;
ll at;
std::string h;
ll dp[15][15][25][3];
ll calc(ll f , ll s , ll len , ll bk){
    if(len >= h.length()){
        return 1;
    }
    if(dp[f][s][len][bk] != -1){
        return dp[f][s][len][bk];
    }
    ll res = 0;
    if(bk){
        for(ll i = 0;9>=i;i++){
            if(i != f && i != s){
                res+=calc(s , i , len + 1 , bk);
            }
        }
    }
    else{
        ll ss = h[len] - '0';
        for(ll i = 0;ss>i;i++){
            if(i != f && i != s){
                res+=calc(s , i , len+1 , 1);
            }
        }
        if(ss != f && ss != s){
            res+=calc(s , ss , len+1 , 0);
        }
    }
    dp[f][s][len][bk] = res;
    return dp[f][s][len][bk];
}
ll gt(std::string d){
    ll res = 1;
    ll bf = d[0] - '0';
    h = d;
    memset(dp , -1 , sizeof(dp));
    for(ll i = 1;bf >=i;i++){
        res+=calc(i , i , 1 , i!=bf);
    }
    for(ll bn = 2;d.length() >= bn;bn++){
        for(ll i = 1;9>=i;i++){
            res+=calc(i , i , bn , 1);
        }
    }
    return res;
}
void solve(){
    std::cin >> at >> b;
    at--;
    if(at < 0){
        std::cout << gt(b) << "\n";
        return;
    }
    a = std::to_string(at);
    ll ans = gt(b) - gt(a);
    std::cout << ans << "\n";
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0; 
}

Compilation message

numbers.cpp:12:1: warning: "/*" within comment [-Wcomment]
   12 | /**/
      |  
numbers.cpp: In function 'll calc(ll, ll, ll, ll)':
numbers.cpp:37:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(len >= h.length()){
      |        ~~~~^~~~~~~~~~~~~
numbers.cpp: In function 'll gt(std::string)':
numbers.cpp:73:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   73 |     for(ll bn = 2;d.length() >= bn;bn++){
      |                   ~~~~~~~~~~~^~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:96:8: warning: unused variable 'o' [-Wunused-variable]
   96 |     ll o = 1;
      |        ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 0 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 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

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 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 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 0 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 0 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 344 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 0 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 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 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