oj.uz

답안 #779905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779905 2023-07-12T02:25:08 Z vjudge1 Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 5 ms 620 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
//#pragma expected_value
//#pragma isolated_call
//#pragma disjoint

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;
using namespace std;

#define int long long
//#define double long double
#define Fi first
#define Se second
#define Rep(i,a,b) for (int i=a;i<=b;++i)
#define Repu(i,b,a) for (int i=b;i>=a;--i)
#define pb push_back
#define ms(a,i) memset(a,i,sizeof(a))
#define sz size()
#define mp make_pair
#define endl '\n'
#define sef setprecision(6)<<fixed
#define cer cout<<"cak"<<endl;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<double> va;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<va> vva;

//const double EPS=1e-9;
const double PI=acos(-1);
const long long oo=1e18;
const int MN=2e5+5;
const int mod=1e9+7;

using cd=complex<double>;

//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> index_set;

int l,r;

string chuyenhoa(int x) {
	string s="";
	if(x==0) s='0';
	while(x>0) {
		s = char(x%10+'0') + s;
		x/=10;
	}
	s='0'+s;
	return s;
}

int dp[25][10][10][10][2]; // fixed cac chu so dau

int solve(string s) {
	Rep(i,0,s.sz-1) Rep(digit,0,9) Rep(p1,0,9) Rep(p2,0,9) Rep(bit1,0,1) dp[i][digit][p1][p2][bit1] = 0;
	dp[0][0][0][0][1] = 1;

	Rep(i,1,1) Rep(p1,0,9) Rep(p2,0,9)
	{
		Rep(digit,1,9) if(digit!=p1 and digit!=p2)
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][0];
		}

		if(s[i]-'0' != 0) {
			Rep(chon,0,9) dp[i][s[i]-'0'][p1][p2][1] += dp[i-1][p1][p2][chon][1];
		}

		Rep(digit,1,9) if(digit!=p1 and digit!=p2 and digit < s[i]-'0')
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][1];
		}
	}

	Rep(i,2,2) Rep(p1,0,9) Rep(p2,0,9)
	{
		Rep(digit,0,9) if(digit!=p1)
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][0];
		}

		if(s[i]-'0' != p1) {
			Rep(chon,0,9) dp[i][s[i]-'0'][p1][p2][1] += dp[i-1][p1][p2][chon][1];
		}

		Rep(digit,0,9) if(digit!=p1 and digit < s[i]-'0')
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][1];
		}
	}

	Rep(i,3,s.sz-1) Rep(p1,0,9) Rep(p2,0,9) 
	{
		Rep(digit,0,9) if(digit!=p1 and digit!=p2)
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][0];
		}

		if(s[i]-'0' != p1 and s[i]-'0' != p2) {
			Rep(chon,0,9) dp[i][s[i]-'0'][p1][p2][1] += dp[i-1][p1][p2][chon][1];
		}

		Rep(digit,0,9) if(digit!=p1 and digit!=p2 and digit < s[i]-'0')
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][1];
		}
	}

	int ans = 0;
	Rep(p1,0,9) Rep(p2,0,9) Rep(p3,0,9)
	{
		ans += dp[s.sz-1][p1][p2][p3][0] + dp[s.sz-1][p1][p2][p3][1];
	}

	return ans;
}

int pre[20];

int dem(int x) {
	if(x<0) return 0;
	if(x<=9) return x+1;
	int ans = solve(chuyenhoa(x));
	int power=10; int cnt=1;
	while(power-1<x) {
		ans+=pre[cnt];
		power*=10;
		cnt++;
	}
	return ans;
}

signed main() {
  	//freopen(".inp","r",stdin); freopen(".out","w",stdout);
  	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin>>l>>r;

	int power=10;
	Rep(i,2,18) {
		power*=10;
		pre[i] = solve(chuyenhoa(power-1));
	}
	pre[1] = 10;

	cout<<dem(r) - dem(l-1);
}

Compilation message

numbers.cpp: In function 'long long int solve(std::string)':
numbers.cpp:18:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define Rep(i,a,b) for (int i=a;i<=b;++i)
......
   61 |  Rep(i,0,s.sz-1) Rep(digit,0,9) Rep(p1,0,9) Rep(p2,0,9) Rep(bit1,0,1) dp[i][digit][p1][p2][bit1] = 0;
      |      ~~~~~~~~~~                   
numbers.cpp:61:2: note: in expansion of macro 'Rep'
   61 |  Rep(i,0,s.sz-1) Rep(digit,0,9) Rep(p1,0,9) Rep(p2,0,9) Rep(bit1,0,1) dp[i][digit][p1][p2][bit1] = 0;
      |  ^~~
numbers.cpp:18:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define Rep(i,a,b) for (int i=a;i<=b;++i)
......
   98 |  Rep(i,3,s.sz-1) Rep(p1,0,9) Rep(p2,0,9)
      |      ~~~~~~~~~~                   
numbers.cpp:98:2: note: in expansion of macro 'Rep'
   98 |  Rep(i,3,s.sz-1) Rep(p1,0,9) Rep(p2,0,9)
      |  ^~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 3 ms 544 KB Output is correct
18 Correct 4 ms 596 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 3 ms 596 KB Output is correct

Subtask #2
75.0 / 75.0

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