oj.uz

Submission #199449

# Submission time Handle Problem Language Result Execution time Memory
199449 2020-02-01T12:50:56 Z TadijaSebez Palindrome-Free Numbers (BOI13_numbers) C++11
100 / 100
 9 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll dp[10][10][2],tmp[10][20][2];
void Clear(){
	for(int j=0;j<10;j++)
		for(int k=0;k<10;k++)
			for(int l=0;l<2;l++)
				dp[j][k][l]=0;
}
void Copy(){
	for(int j=0;j<10;j++)
		for(int k=0;k<10;k++)
			for(int l=0;l<2;l++)
				tmp[j][k][l]=dp[j][k][l];
}
ll Solve(ll x){
	//printf("%lld\n",x);
	if(x==0)return 1;
	ll y=x;
	vector<int> cif;
	while(x)cif.pb(x%10),x/=10;
	reverse(cif.begin(),cif.end());
	ll mul=1;for(int i=1;i<cif.size();i++)mul*=10;
	ll ans=Solve(mul-1);
	if(cif.size()==1)return y+ans;
	Clear();
	for(int i=1;i<=9;i++)for(int j=0;j<=9;j++)if(i!=j){
		if(i==cif[0] && j==cif[1])dp[i][j][1]=1;
		else if(i<cif[0] || i==cif[0] && j<cif[1])dp[i][j][0]=1;
	}
	for(int len=2;len<cif.size();len++){
		Copy();
		Clear();
		for(int i=0;i<=9;i++)for(int j=0;j<=9;j++){
			for(int k=0;k<=9;k++)if(j!=i && j!=k){
				dp[i][j][0]+=tmp[k][i][0];
				if(j<cif[len])dp[i][j][0]+=tmp[k][i][1];
			}
		}
		if(cif[len]!=cif[len-1] && cif[len]!=cif[len-2])dp[cif[len-1]][cif[len]][1]=tmp[cif[len-2]][cif[len-1]][1];
	}
	for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)ans+=dp[i][j][0]+dp[i][j][1];
	//printf("%lld %lld\n",y,ans);
	return ans;
}
int main(){
	ll l,r;
	scanf("%lld %lld",&l,&r);
	printf("%lld\n",Solve(r)-(l>0?Solve(l-1):0));
	return 0;
}

Compilation message

numbers.cpp: In function 'long long int Solve(long long int)':
numbers.cpp:25:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  ll mul=1;for(int i=1;i<cif.size();i++)mul*=10;
                       ~^~~~~~~~~~~
numbers.cpp:31:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   else if(i<cif[0] || i==cif[0] && j<cif[1])dp[i][j][0]=1;
numbers.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int len=2;len<cif.size();len++){
                ~~~^~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&l,&r);
  ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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