제출 #636288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636288		destructor_19	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	388 KiB

numbers

# include <bits/stdc++.h>
using namespace std;

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define eb          emplace_back
#define endl		'\n'
#define max(a,b)	((a)>(b)?(a):(b))
#define min(a,b)	((a)<(b)?(a):(b))
#define vi          vector<int>
#define vii         vector<pair<int, int> >
#define mp          make_pair
#define mem1(a)     memset((a),-1,sizeof(a))
#define mem0(a)     memset((a),0,sizeof(a))
#define memf(a)     memset((a),false,sizeof(a))
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    (a)*((b)/gcd((a),(b)))
#define DECIMAL(n)  cout << fixed ; cout << setprecision(n);
#define FAST        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mi          map<int,int>
#define sz(x)       (ll)(x).size()
#define rep(i,a,b)  for(int i=(a);i<(b);i++)
#define pii         pair<int,int>

long long dp[19][2][2][11][11];

long long rec(int indx, int tight, int started, int prev, int pprev, string num)
{
	if (indx == (int)num.size())
		return 1;
	long long &ans = dp[indx][tight][started][prev][pprev];
	if (ans != -1)
		return ans;
	ans = 0;
	int up = num[indx] - '0';
	if (tight)
		up = 9;
	for (int i = 0; i <= up; i++)
	{
		if ((prev == 10 || i != prev) && (pprev == 10 || i != pprev))
		{
			int ntight = tight | i < (num[indx] - '0');
			int nstarted = started | (i > 0);
			if (!started && !i)
			{
				ans += rec(indx + 1, ntight, nstarted, prev, pprev, num);
			}
			else
			{
				ans += rec(indx + 1, ntight, nstarted, i, prev, num);
			}
		}
	}
	return ans;
}

int solve()
{
	long long l, r;
	cin >> l >> r;
	mem1(dp);
	string R = to_string(r);
	long long ans = rec(0, 0, 0, 10, 10, R);
	mem1(dp);
	string L = to_string(--l);
	ans -= rec(0, 0, 0, 10, 10, L);
	cout << ans;

	return 0;
}
signed main()
{
	FAST
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int t = 1;
	// cin>>t;
	while (t)
	{
		solve();
		t--;
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

numbers.cpp: In function 'long long int rec(int, int, int, int, int, std::string)':
numbers.cpp:46:27: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   46 |    int ntight = tight | i < (num[indx] - '0');
      |                         ~~^~~~~~~~~~~~~~~~~~~

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