oj.uz

Submission #553387

# Submission time Handle Problem Language Result Execution time Memory
553387 2022-04-25T16:58:05 Z new_acc Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 1 ms 468 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 468 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Correct 1 ms 468 KB Output is correct
44 Correct 1 ms 468 KB Output is correct
45 Correct 1 ms 468 KB Output is correct