Submission #553387

#	Time	Username	Problem	Language	Result	Execution time	Memory
553387		new_acc	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	1 ms	468 KiB

numbers

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=21;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
ll dp[N][N][N],dp2[N][N][N][2];
ll cnt(ll a){
	if(a<0) return 0;
	string s="";
	ll pp=a;
	while(a>0){
		s+=char((a%10)+48);
		a/=10;
	}
	reverse(s.begin(),s.end());
	if(s.size()<=2){
		ll res=0;
		for(int i=0;i<=pp;i++){
			int xd=i,pop=-1;
			bool ok=1;
			while(xd>0){
				if(xd%10==pop) ok=0;
				pop=xd%10;
				xd/=10;
			}
			if(ok) res++;
		}
		return res;
	}
	ll res=10;
	for(int i=2;i<=s.size();i++){
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++) dp[i][j][k]=0,dp2[i][j][k][1]=0,dp2[i][j][k][0]=0;;
	}
	for(int i=1;i<=9;i++){
		for(int j=0;j<=9;j++){
			if(i==j) dp[2][i][j]=0;
			else dp[2][i][j]=1;
		}
	}
	for(int i=3;i<s.size();i++){
		for(int j=0;j<=9;j++){
			for(int k=0;k<=9;k++){
				for(int x=0;x<=9;x++){
					if(x==k or x==j) continue;
					dp[i][k][x]+=dp[i-1][j][k];
				}
			}
		}
	}
	for(int i=2;i<s.size();i++){
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++) res+=dp[i][j][k];
	}
	for(int i=1;i<=9;i++){
		for(int j=0;j<=9;j++){
			if(i==j){
				dp2[2][i][j][0]=0,dp2[2][i][j][1]=0;
				continue;
			}
			int f=s[0]-48,sc=s[1]-48;
			if(i>f) dp2[2][i][j][0]=0,dp2[2][i][j][1]=0;
			else{
				if(i==f){
					if(j>sc) dp2[2][i][j][0]=0,dp2[2][i][j][1]=0;
					else{
						if(j==sc) dp2[2][i][j][0]=1,dp2[2][i][j][1]=0;
						else dp2[2][i][j][0]=0,dp2[2][i][j][1]=1;
					}
				}else dp2[2][i][j][0]=0,dp2[2][i][j][1]=1;
			}
		}
	}
	for(int i=3;i<=s.size();i++){
		for(int j=0;j<=9;j++){
			for(int k=0;k<=9;k++){
				int curr=s[i-1]-48;
				if(curr==j or curr==k) continue;
				dp2[i][k][curr][0]+=dp2[i-1][j][k][0];
			}
		}
		for(int j=0;j<=9;j++){
			for(int k=0;k<=9;k++){
				for(int x=0;x<=9;x++){
					if(x==k or x==j) continue;
					dp2[i][k][x][1]+=dp2[i-1][j][k][1];
					int curr=s[i-1]-48;
					if(x<curr) dp2[i][k][x][1]+=dp2[i-1][j][k][0];
				}
			}
		}
	}
	for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) res+=dp2[s.size()][i][j][0]+dp2[s.size()][i][j][1];
	return res;
}
void solve(){
	ll a,b;
	cin>>a>>b;
	cout<<cnt(b)-cnt(a-1)<<"\n";
}
int main(){
	solve();
}

Compilation message (stderr)

numbers.cpp: In function 'll cnt(ll)':
numbers.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=2;i<=s.size();i++){
      |              ~^~~~~~~~~~
numbers.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=3;i<s.size();i++){
      |              ~^~~~~~~~~
numbers.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=2;i<s.size();i++){
      |              ~^~~~~~~~~
numbers.cpp:88:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=3;i<=s.size();i++){
      |              ~^~~~~~~~~~

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