Submission #154253

#	Time	Username	Problem	Language	Result	Execution time	Memory
154253		Kamisama	Palindrome-Free Numbers (BOI13_numbers)	C++14	0 / 100	7 ms	1192 KiB

numbers

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <chrono>
#include <sstream>
#include <cstring>
#define Kami
#define taskname "TEST"
using namespace std;

long long f[20][10][10][20][2];
string s;

inline long long Dp(const int &pos, const int &p1, const int &p2, const int &curLen, const bool &pref){
    if(pos>=(int)s.size()) return 1;
    long long &res=f[pos][p1][p2][curLen][pref];
    if(res!=-1) return res;
    res=0;
    int lim=pref? s[pos]-'0' : 9;
    for(int x=0;x<=lim;x++){
        bool newPref=(pref && x==lim);
        if(curLen==0){
            if(x) res+=Dp(pos+1,0,x,curLen+1,newPref);
            else res+=Dp(pos+1,0,x,curLen,newPref);
        } else if(x!=p2 && ((curLen>1 && x!=p1) || curLen==1)){
            res+=Dp(pos+1,p2,x,curLen+1,newPref);
        }
    }
    return res;
}

inline long long Solve(const long long &x){
    stringstream ss;
    ss<<x; ss>>s;
    memset(f,-1,sizeof(f));
    return Dp(0,0,0,0,1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); if(fopen(taskname".INP","r"))
    freopen(taskname".INP","r",stdin),
    freopen(taskname".OUT","w",stdout);
    #ifdef Kami
    auto start=chrono::steady_clock::now();
    #endif

    long long a,b;
    cin>>a>>b;
    cout<<Solve(b)-Solve(a-1);

    #ifdef Kami
    auto end=chrono::steady_clock::now();
    cerr<<"\nIn milliseconds : "
        <<chrono::duration_cast<chrono::milliseconds>(end-start).count();
    cerr<<'\n'<<"In seconds : "<<fixed<<setprecision(3)
        <<(double)chrono::duration_cast<chrono::milliseconds>(end-start).count()/1000<<'\n';
    #endif

    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:42:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(taskname".INP","r",stdin),
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
     freopen(taskname".OUT","w",stdout);
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:42:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

• Subtask 1: 0 / 25
• Subtask 2: 0 / 75