oj.uz

답안 #534935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534935 2022-03-09T07:15:07 Z faik Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 3 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001
#define int ll

#define MAX 100000
#define MAXLOG 17

#define int ll

typedef pair<int,int> pii;

pii bruh(int x){
	pii ret = {1,1};
	while(x > 9){
		x/=10;
		ret.first++;
		ret.second *= 10;
	}
	return ret;
}

int powon[19];
int dp[19][2][11][11];

int pre(int x){
	if(x < 0)
		return 0;
	for(int i = 0;i < 19;i++)
		for(int j = 0;j < 2;j++)
			for(int k = 0;k < 11;k++)
				for(int l = 0;l < 11;l++)
					dp[i][j][k][l] = 0;

	pii cum = bruh(x);

	dp[cum.first][1][10][10] = 1;

	for(int i = cum.first;i >= 1;i--)
		for(int j = 0;j < 2;j++)
			for(int k = 0;k < 11;k++)
				for(int l = 0;l < 11;l++){
					if(dp[i][j][k][l] == 0)
						continue;
					
					int mx = 9;
					if(j == 1){
						mx = x/powon[i-1]%10;
					}

					int mn = 0;
					if(k == 10 && i > 1)
						mn = 1;

					for(int m = mx;m >= mn;m--){
						if(m != k && m != l){
							int flag = j && (m == x/powon[i-1]%10);
							dp[i-1][flag][m][k] += dp[i][j][k][l];
							// cout << i-1 << ' ' << flag << ' ' << m << ' ' << k << '+' << dp[i][j][k][l] << '\n';
						}
					}
					if(i > 1 && k == 10){
						dp[i-1][0][10][k] += dp[i][j][k][l];
						// cout << i-1 << ' ' << 0 << ' ' << 10 << ' ' << k << '+' << dp[i][j][k][l] << '\n';
					}
				}
	
	int ret = 0;
	for(int j = 0;j < 2;j++)
			for(int k = 0;k < 10;k++)
				for(int l = 0;l < 11;l++){
					// if(dp[0][j][k][l] > 0)
					// 	cout << 0 << ' ' << j << ' ' << k << ' ' << l << ' ' << dp[0][j][k][l] << '\n';
					ret += dp[0][j][k][l];
				}

	return ret;
}	

void solve(){
//#define TEST
	int curr = 1;
	for(int i = 0;i < 19;i++){
		powon[i] = curr;
		curr *= 10;
	}

	// for(int i = 1;i < 100000;i++){
	// 	if(pre(i) != brute(i)){
	// 		cout << i << ' ' << pre(i) << ' ' << brute(i) << '\n';
	// 	}
	// }
	int a,b;cin >> a >> b;
	// cout << a << ' ' << b << '\n';
	cout << pre(b)-pre(a-1);
}

signed main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
#ifdef DEBUG
	freopen("i.txt","r",stdin);
	freopen("o.txt","w",stdout);
#endif
	int t = 1;
#ifdef TEST
	cin >> t;
#endif
	while(t--){
		solve();
	}

	return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 304 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 320 KB Output is correct
13 Correct 1 ms 268 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 3 ms 332 KB Output is correct
19 Correct 2 ms 308 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 1 ms 296 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 316 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 312 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 312 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 312 KB Output is correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Correct 1 ms 316 KB Output is correct
42 Correct 1 ms 332 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 1 ms 332 KB Output is correct
45 Correct 1 ms 332 KB Output is correct