Submission #232021

#	Time	Username	Problem	Language	Result	Execution time	Memory
232021		mosiashvililuka	Palindrome-Free Numbers (BOI13_numbers)	C++14	73.75 / 100	5 ms	420 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
long long c,d,e,zx,xc,i,j,ii,jj,dp[22][12][12],p[22],pi,pas;
string a,b,aa,bb;
void rec(long long q, bool bo1, bool bo2){
	//cout<<q<<" x "<<bo1<<" "<<bo2<<"  "<<pi<<endl;
	//for(long long h=1; h<=pi; h++) cout<<p[h]<<" kala ";
	//cout<<endl;
	if(q>=a.size()){
		//cout<<"CAT"<<endl<<endl<<endl;
		pas++;
		return;
	}
	if(bo1==1&&bo2==1){
		//cout<<"DOG"<<endl<<endl<<endl;
		if(a.size()-q>=2){
		for(i=0; i<=9; i++){
			for(j=0; j<=9; j++){
				if(i==j) continue;
				if(p[pi]==i||p[pi]==j||p[pi-1]==i) continue;
				pas+=dp[a.size()-q][i][j];
			}
		}
		}else{
			for(i=0; i<=9; i++){
				if(i!=p[pi]&&i!=p[pi-1]) pas+=dp[1][i][0];
			}
		}
		return;
	}
	for(long long h=0; h<=9; h++){
		if(bo1==0&&h<a[q]-'0') continue;
		if(bo2==0&&h>b[q]-'0') continue;
		if(pi>0&&h==p[pi]) continue;
		if(pi>1&&h==p[pi-1]) continue;
		bool qw=bo1,we=bo2;
		if(h>a[q]-'0') qw=1;
		if(h<b[q]-'0') we=1;
		pi++;p[pi]=h;
		rec(q+1,qw,we);
		pi--;
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	while(a.size()<b.size()) a.insert(0,"0");
	dp[0][0][0]=1;
	for(i=0; i<=9; i++) dp[1][i][0]=1;
	for(i=2; i<=19; i++){
		for(ii=0; ii<=9; ii++){
			for(j=0; j<=9; j++){
				if(ii==j) continue;
				if(i==2){
					dp[i][ii][j]+=dp[i-1][j][0];
					continue;
				}
				for(jj=0; jj<=9; jj++){
					if(ii==jj||j==jj) continue;
					dp[i][ii][j]+=dp[i-1][j][jj];
				}
			}
		}
	}
	p[0]=-1;
	rec(0,0,0);
	cout<<pas;
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'void rec(long long int, bool, bool)':
numbers.cpp:9:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(q>=a.size()){
     ~^~~~~~~~~~

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