Submission #78921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
78921	2018-10-09T15:22:51 Z	doowey	Palindrome-Free Numbers (BOI13_numbers)	C++14	80 / 100	3 ms	748 KB

numbers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin(),(x).end())
#define len(x) ((int)(x).size())

const int N = 19;
ll dp[N][11][11];

ll tot[N];

void init(){
	for(int i = 1;i < 10; i ++ )
		dp[1][i][i] = 1;
	tot[1] = 9;
	tot[2] = 9 * 9;
	for(int i = 0; i < 10; i ++ ){
		for(int j = 0;j < 10; j ++ ){
			if(i != j and i > 0)
				dp[2][i][j] = 1;
		}
	}
	for(int num = 2; num < N - 1; num ++ ){
		for(int x = 0; x < 10; x ++ ){
			for(int z = 0;z < 10; z ++ ){
				for(int nx = 0; nx < 10; nx ++ ){
					if(nx != z and nx != x){
						dp[num + 1][z][nx] += dp[num][x][z];
						tot[num + 1] += dp[num + 1][z][nx];
					}
				}
			}
		}
	}
}

ll calc(ll xy){
	if(xy == -1)
		return 0;
	vector<int> idx;
	while(xy > 0){
		idx.push_back(xy % 10);
		xy /= 10;
	}
	ll dp2[20][10][10][2];
	memset(dp2, 0, sizeof dp2);
	int n = idx.size();
	int las;
	ll ans = 1;
	for(int i = 1; i <= n; i ++ ){
		las = idx.back();
		idx.pop_back();
		if(i != n)
			ans += tot[i];
		if(i == 1){
			for(int nx = 1; nx <= las; nx ++ ){
				dp2[i][nx][0][nx < las] = 1; 
			}
		}
		else if(i == 2){
			for(int pv = 1; pv <= 9; pv ++ ){
				for(int nx = 0; nx <= 9 ; nx ++ ){
					if(pv != nx){
						if(nx < las){
							dp2[i][pv][nx][1] += dp2[i - 1][pv][0][0] + dp2[i - 1][pv][0][1]; 
						}
						else if(nx == las){
							dp2[i][pv][nx][0] += dp2[i - 1][pv][0][0];
							dp2[i][pv][nx][1] += dp2[i - 1][pv][0][1];
						}
						else{
							dp2[i][pv][nx][1] += dp2[i - 1][pv][0][1];
						}
					}
				}
			}
		}
		else{
			for(int y = 0 ; y <= 9; y ++ ){
				for(int z = 0 ; z <= 9; z ++ ){
					for(int nx = 0; nx < 10; nx ++ ){
						if(nx == y or nx == z or y == z)
							continue;
						if(nx < las){
							dp2[i][z][nx][1] += dp2[i - 1][y][z][0] + dp2[i - 1][y][z][1];
						}
						else if(nx == las){
							dp2[i][z][nx][0] += dp2[i - 1][y][z][0];
							dp2[i][z][nx][1] += dp2[i - 1][y][z][1];
						}
						else{
							dp2[i][z][nx][1] += dp2[i - 1][y][z][1];
						}
					}
				}
			}
		}
	}
	for(int y = 0; y <= 9; y ++ ){
		for(int z = 0;z <= 9; z ++ ){
			for(int d = 0; d < 2; d ++ ){
				ans += dp2[n][y][z][d];
			}
		}
	}
	return ans;
}

int main(){
	fastIO;
	init();
	ll a, b;
	cin >> a >> b;
	cout << calc(b) - calc(a - 1);
	return 0;
}

Subtask #1

20.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	520 KB	Output is correct
4	Incorrect	2 ms	520 KB	Output isn't correct
5	Correct	2 ms	520 KB	Output is correct
6	Correct	2 ms	600 KB	Output is correct
7	Correct	2 ms	600 KB	Output is correct
8	Correct	2 ms	660 KB	Output is correct
9	Correct	2 ms	676 KB	Output is correct
10	Correct	2 ms	676 KB	Output is correct
11	Correct	2 ms	676 KB	Output is correct
12	Correct	2 ms	676 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Incorrect	2 ms	676 KB	Output isn't correct
15	Incorrect	2 ms	676 KB	Output isn't correct
16	Correct	2 ms	676 KB	Output is correct
17	Correct	2 ms	676 KB	Output is correct
18	Correct	2 ms	676 KB	Output is correct
19	Correct	2 ms	676 KB	Output is correct
20	Incorrect	2 ms	676 KB	Output isn't correct

Subtask #2

60.0 / 75.0

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