oj.uz

Submission #1075584

# Submission time Handle Problem Language Result Execution time Memory
1075584 2024-08-26T07:52:50 Z huyngodzz Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 3 ms 3016 KB 
    ///huynhocute123///
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define pb push_back
#define pi M_PI
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = b; i >= a; --i)
#define ALL(v) v.begin(),v.end()
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
//random_device rd;
//mt19937 rng(rd());
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define int long long
const int maxN = 1e5 ;
const int  modd = 1e9 + 7;
const int base = 2309;
const int MAX = 1e9+9;
void minimize(int &u, int v){
    if(v < u) u = v;
}
void maximize(int &u, int v){
    if(v > u) u = v;
}
int n, k, t, m, res, a[maxN];
long long dp[20][3][12][12][3];
long long l, r;
bool vis[maxN];
vector<int> e[maxN];
void pre(long long val){
    n =0;
    while(val){
        a[++n] = val%10;
        val /=10;
    }
    reverse(a+1, a+1 +n);
}
long long calc(int id ,int tight, int prev1, int prev2, int ok){
    if(id > n)return 1;
    if(dp[id][tight][prev1][prev2][ok] != -1)return dp[id][tight][prev1][prev2][ok];
    long long ans =0;
    int lim= (tight == 0 ? 9 : a[id]);
    FOR(i, 0 ,lim){
        int Ntight = (i < lim ? 0 : tight);
        if(i == prev1 || i == prev2 )continue;
        int Nok =  ok| (i > 0);
        int P1 = prev2;
        int P2= i;
        if(!Nok)ans += calc(id +1 ,0, 10 , 10, 0 );
        else  ans += calc(id +1, Ntight , P1, P2,Nok);
    }
    return dp[id][tight][prev1][prev2][ok] = ans;

}
long long get(long long val){
    pre(val);
    memset(dp, -1 ,sizeof(dp));
    return calc(1, 1, 10, 10, 0 );
}
void solve(){
    cin >> l >> r;
    cout << get(r) - get(l -1);

}
signed main(){
//    freopen("name.inp","r",stdin);
//    freopen("name.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    inp("task.inp");
    t = 1;
   // cin >> t;
    while( t-- )solve();

}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:13:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
numbers.cpp:76:5: note: in expansion of macro 'inp'
   76 |     inp("task.inp");
      |     ^~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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