Submission #553386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553386	2022-04-25T16:39:12 Z	new_acc	Palindrome-Free Numbers (BOI13_numbers)	C++14	80 / 100	1 ms	468 KB

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="";
	int 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){
						dp[i][k][x]=0;
					 	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:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=2;i<s.size();i++){
      |              ~^~~~~~~~~
numbers.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i=3;i<=s.size();i++){
      |              ~^~~~~~~~~~

Subtask #1

20.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	Incorrect	0 ms	340 KB	Output isn't 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	1 ms	212 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Incorrect	0 ms	340 KB	Output isn't correct
15	Incorrect	0 ms	340 KB	Output isn't 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	Incorrect	0 ms	340 KB	Output isn't correct

Subtask #2

60.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	Incorrect	0 ms	340 KB	Output isn't correct
6	Correct	1 ms	340 KB	Output is correct
7	Incorrect	1 ms	340 KB	Output isn't correct
8	Incorrect	0 ms	340 KB	Output isn't correct
9	Incorrect	0 ms	340 KB	Output isn't correct
10	Incorrect	0 ms	340 KB	Output isn't correct
11	Correct	1 ms	340 KB	Output is correct
12	Incorrect	0 ms	340 KB	Output isn't correct
13	Incorrect	0 ms	340 KB	Output isn't correct
14	Incorrect	0 ms	340 KB	Output isn't correct
15	Incorrect	1 ms	340 KB	Output isn't 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	468 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