Submission #1173316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173316		Nurislam	Palindrome-Free Numbers (BOI13_numbers)	C++20	30.83 / 100	1096 ms	436 KiB

numbers

#include <bits/stdc++.h>

using namespace std;


#define int long long
//#define pb push_back

int inf = 1e18; 

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

void solve(){
	
	vector<int> pw(19, 1);
	for(int i = 1; i < 19; i ++ ) pw[i] = pw[i-1] * 10;
	
	auto dig = [&] (int &va, int id) -> int {
		return (va / pw[id]) %10;
	};
	auto get = [&](int lim) -> int {
		if(lim < 0)return 0;
		int ans = 1;
		int x = 1;
		while(x <= lim) {
			int len = 18;
			while(x / pw[len] == 0)len--;
			
			bool valid = 1;
			int d = 0;
			for(int i = len-1; i >= 0; i -- ) {
				if(dig(x, i+1) == dig(x, i)) {
					d = i;
					valid = 0;
				}
				if(i + 2 <= len && dig(x, i+2) == dig(x, i)){
					d = i;
					valid = 0;
				}
			}
			if(valid) ans ++ ;
			
			x = (x/pw[d] + 1) * pw[d];
		}
		return ans;
	};
	
	int b, a;
	cin >> b >> a;
	cout << get(a) - get(--b) << '\n';
};



signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

• Subtask 1: 22.5 / 25
• Subtask 2: 8.3333 / 75