Submission #779719

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
779719	2023-07-11T17:32:45 Z	SteGG	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	468 KB

numbers

//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)

template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
	output << "(" << A.first << ", " << A.second <<  ")";
	return output;
}

template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
	int n = arr.size();
	output << "[";
	for(int i = 0; i < n; i++){
		output << arr[i];
		if(i != n - 1) output << ", ";
	}
	output << "]";
	return output;
}

template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
	output << "{";
	for(auto it = s.begin(); it != s.end(); it++){
		if(it != s.begin()) output << ", ";
		output << (*it);
	}
	output << "}";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
	output << "{";
	for(auto it = m.begin(); it != m.end(); it++){
		if(it != m.begin()) output << ", ";
		output << "(" << it->first << " : " << it->second << ")";
	}
	output << "}";
	return output;
}

template<class TH>
void _dbg(const char *sdbg, TH h){
	cout << sdbg << " = " << h << endl;
}

template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
	while(*sdbg != ',')cout << *sdbg++;
	cout << " = " << h << "\n";
	_dbg(sdbg+1, a...);
}

template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
	cout << '[' << index << "] = " << arr[index] << endl;
}

template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
	cout << '[' << index << ']';
	_dbg_arr(arr[index], args...);
}

//open file
#define taskname "" //name input and output file

#ifdef SteGG
void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		//freopen("output.out", "w", stdout);
	}
}
#else
void open(){
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}
#endif

//initialize
#define testcase \
	long long test; \
	cin >> test; \
	for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()

const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 1e5 + 5;
//const int base = ;
string l, r;
int n;
int dp[20][2][2][11][11][2];

//others struct or class

//others function

//others init

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	open();
	cin >> l >> r;
	n = r.size();
	while(l.size() < n){
		l = '0' + l;
	}

	memset(dp, -1, sizeof(dp));

	auto solve = [&](auto &&solve, int index, int checkl, int checkr, int l_1, int l_2, int in_num) -> int {
		if(index == n) return 1;

		if(dp[index][checkl][checkr][l_1 + 1][l_2 + 1][in_num] != -1) return dp[index][checkl][checkr][l_1 + 1][l_2 + 1][in_num];

		int result = 0;

		for(int d = 0; d < 10; d++){
			if(d == l_1 || d == l_2) continue;
			if(checkl && l[index] - '0' > d) continue;
			if(checkr && r[index] - '0' < d) continue;
			in_num |= (d != 0);
			if(in_num){
				result += solve(solve, index + 1, checkl & (l[index] - '0' == d), checkr & (r[index] - '0' == d), l_2, d, in_num);
			}else{
				result += solve(solve, index + 1, checkl & (l[index] - '0' == d), checkr & (r[index] - '0' == d), l_1, l_2, in_num);
			}
		}

		return dp[index][checkl][checkr][l_1 + 1][l_2 + 1][in_num] = result;
	};

	cout << solve(solve, 0, 1, 1, -1, -1, 0) << endl;

	return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:143:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  143 |  while(l.size() < n){
      |        ~~~~~~~~~^~~
numbers.cpp: In function 'void open()':
numbers.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

25.0 / 25.0

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

Subtask #2

75.0 / 75.0

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