Submission #51538

#	Time	Username	Problem	Language	Result	Execution time	Memory
51538		WA_TLE	Palindrome-Free Numbers (BOI13_numbers)	C++14	73.75 / 100	3 ms	1080 KiB

numbers

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
llint solve(llint in){
	
	if(in==0){return 0;}
	array<llint,100>dp={0};
	int keta[22]={0};
	for(int h=0;h<22;h++){keta[h]=in%10;in/=10;}
	bool paf=true;//ここまでparindrome-freeですか?
	int h=21,i,j;
	while(keta[h]==0){h--;}
	int turn=0;
	for(;h>=0;h--){
		array<llint,100>ddp={0};
		for(i=0;i<100;i++){//繊維元
			for(j=0;j<10;j++){//繊維先
				if(i%10==j||((turn>1)&&(i/10==j))){continue;}//だめ
				ddp[(i%10)*10 +j]+=dp[i];
				
			}
		}
		if(paf){
			int mae=keta[h+2]*10+keta[h+1];
			for(j=0;j<keta[h];j++){
				if(turn==0&&j==0){continue;}
				if(turn==1){mae+=100;}
				if(mae/10==j||mae%10==j){continue;}//だめ
				ddp[(mae%10)*10 +j]++;
			}
		}
		if(keta[h+1]==keta[h]||(turn>1&&keta[h+2]==keta[h])){paf=false;}
		dp=ddp;
		dp[0]++;
		turn++;
	}
	llint ans=0;
	for(i=0;i<100;i++){ans+=dp[i];}
	return ans;
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	llint a,b;cin>>a>>b;
	cout<<solve(b+1)-solve(a)<<endl;
	return 0;
}

• Subtask 1: 13.75 / 25
• Subtask 2: 60 / 75