oj.uz

Submission #100771

# Submission time Handle Problem Language Result Execution time Memory
100771 2019-03-14T09:27:31 Z shafinalam Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 4 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5+5;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;

#define  sf scanf
#define  pf printf

#define  input freopen("input.txt","r",stdin)
#define  output freopen("output.txt","w",stdout)

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))

int  Set(int N,int pos){return N=N | (1<<pos);}
int  reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}

int n;
int arr[20];
ll dp[20][2][2][11][11];

ll solve(int pos, int st, int choto, int p1, int p2)
{
    if(pos>=n) return 1;
    if(dp[pos][st][choto][p1][p2]!=-1) return dp[pos][st][choto][p1][p2];
    int lim = (choto) ? arr[pos] : 9;
    ll ret = 0;
    for(int i = 0; i <= lim; i++)
    {
        if(i==p1 || i==p2) continue;
        ret+=solve(pos+1, (i==0 ? st : 1), (i<arr[pos] ? 0 : choto), ((i==0 && !st)?10:i), p1);
        //ret+=solve(pos+1, (i==0?st:1), ((i<arr[pos])?1:choto), )
    }
    return dp[pos][st][choto][p1][p2] = ret;
}
void make_array(ll a)
{
    n = log10(a)+1;
    for(int i = n-1; i >= 0; i--)
    {
        arr[i] = a%10;
        a/=10;
    }
}
int main()
{
    ll a, b;
    sf("%lld%lld", &a, &b);

    if(b==0)
    {
        pf("1\n");
        return 0;
    }
    make_array(b);
    memset(dp, -1, sizeof dp);
    ll ans1 = solve(0, 0, 1, 10, 10);
    if(a==0)
    {
        pf("%lld\n", ans1);
        return 0;
    }
    if(a==1)
    {
        pf("%lld\n", ans1-1);
        return 0;
    }
    make_array(a-1);
    memset(dp, -1, sizeof dp);
    ll ans2 = solve(0, 0, 1, 10, 10);
    ll ans = ans1-ans2;
    cout << ans << '\n';
    return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     sf("%lld%lld", &a, &b);
       ^

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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