oj.uz

Submission #102369

# Submission time Handle Problem Language Result Execution time Memory
102369 2019-03-24T14:11:20 Z groeneprof Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 3 ms 512 KB 
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;

int f(string a){
	//cout<<"------------------------ "<<a<<endl;
	int memo[a.size()+1][11][11][2];
	F(i, a.size()+1) F(j, 11) F(k, 11) F(l, 2){
		memo[i][j][k][l] = 0;
	}
	memo[0][10][10][0] = 1;
	FR(i, 1, a.size()+1){
		F(j, 11){
			F(k, 11){
				F(l, 2){
					F(m, 10) if(m!=j&&m!=k && (l==1||m+'0'<=a[i-1]) && (k!=10 || m!= 0)){
						memo[i][k][m][(int)(l==1||m+'0'<a[i-1])] += memo[i-1][j][k][l];
					}
					if(k == 10 && l == 1){
						memo[i][k][10][1]+=memo[i-1][j][k][0]+memo[i-1][j][k][1];
					}
				}
			}
		}
	}
	int res = 0;
	F(j, 11) F(k,11) F(l, 2){
		P(j<<" "<<k<<" "<<l<<": "<<memo[a.size()][j][k][l]);
		res+=memo[a.size()][j][k][l];
	}
	return res;
}

signed main() {
	ios_base::sync_with_stdio(true);
	cin.tie(0);
	int a, b;
	cin>>a>>b;
	if(b==0) cout<<1;
	else if(a==0) cout<<f(to_string(b));
	else cout<<f(to_string(b))-f(to_string(a-1));
	return 0;
}

Compilation message

numbers.cpp: In function 'long long int f(std::__cxx11::string)':
numbers.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FR(i, a, b) for(int i = (a); i < (b); ++i)
                                        ^
numbers.cpp:6:17: note: in expansion of macro 'FR'
 #define F(i, n) FR(i, 0, n)
                 ^~
numbers.cpp:22:2: note: in expansion of macro 'F'
  F(i, a.size()+1) F(j, 11) F(k, 11) F(l, 2){
  ^
numbers.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FR(i, a, b) for(int i = (a); i < (b); ++i)
                                        ^
numbers.cpp:26:2: note: in expansion of macro 'FR'
  FR(i, 1, a.size()+1){
  ^~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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