Submission #100771

#	Time	Username	Problem	Language	Result	Execution time	Memory
100771		shafinalam	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	4 ms	512 KiB

numbers

#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 (stderr)

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 / 25
• Subtask 2: 75 / 75