Submission #158422

#	Time	Username	Problem	Language	Result	Execution time	Memory
158422		junodeveloper	Palindrome-Free Numbers (BOI13_numbers)	C++14	96.25 / 100	2 ms	380 KiB

numbers

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll N,dp[20][11][11][2],pw[20];
ll go(int pos,int pre, int cur, int eql) {
	if(pos==0) return 1;
	ll& ret=dp[pos][pre][cur][eql];
	if(ret!=-1) return ret;
	ret=0;
	int i,j=N/pw[pos-1]%10;
	if(eql) {
		if(j!=pre && j!=cur)
			ret+=go(pos-1, cur, j, eql);
	}
	for(i=0;i<(eql?j:10);i++) {
		if(i==pre || i==cur) continue;
		ret+=go(pos-1,cur,i,0);
	}
	return ret;
}
ll f(ll n) {
	if(n==0) return 0;
	N=n;
	memset(dp,-1,sizeof(dp));
	ll v=1; int pos=0;
	while(n/v>=10) v*=10, pos++;
	ll ret=0;
	int i,j;
	for(i=pos;i>=0;i--) {
		if(i==pos) ret+=go(i,10,n/v%10,1);
		for(j=1;j<(i==pos?n/v%10:10);j++)
			ret+=go(i,10,j,0);
	}
	return ret;
}
int main() {
	int i;
	pw[0]=1;
	for(i=1;i<20;i++) pw[i]=10*pw[i-1];
	ll a,b;
	scanf("%lld%lld",&a,&b);
	printf("%lld",f(b)-f(a-1));
	return 0;
}

Compilation message (stderr)

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

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