제출 #631445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631445		mousey	Palindrome-Free Numbers (BOI13_numbers)	C++14	96.25 / 100	1 ms	340 KiB

numbers

#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define pdb pair <double, double> 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define endl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll> 
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const ll N=1e6;
ll a, b;

string convert(ll a)
{
	string s="";
	while(a>0)
	{
		s=(char (a%10 + '0'))+s;
		a/=10;
	}
	return s;
}

void input()
{
	cin >> a >> b;
	a--;
}

ll calc(ll a)
{
	string _a=convert(a);
	ll dp[20][10][10][3]={};
	dp[0][0][0][1]=1;
	for(int i = 1; i <= 9; i++)
	{
		if(i<_a[0]-48) dp[1][0][i][0]++;
		if(i==_a[0]-48) dp[1][0][i][1]++;
		if(i>_a[0]-48) dp[1][0][i][2]++;
	}
	
	for(int i = 2; i <= _a.size(); i++)
	{
		for(int j = 0; j < 10; j++)
		{
			for(int l = 0; l < 10; l++)
			{
				for(int k = 0; k < 10; k++)
				{
					if((j==k || j==l || k==l) && i>2) continue;
					if(i==2 && k==l) continue;
					dp[i][l][k][0]+=dp[i-1][j][l][0];
					dp[i][l][k][2]+=dp[i-1][j][l][2];
					if(k==_a[i-1]-48) dp[i][l][k][1]+=dp[i-1][j][l][1];
					if(k<_a[i-1]-48) dp[i][l][k][0]+=dp[i-1][j][l][1];
					if(k>_a[i-1]-48) dp[i][l][k][2]+=dp[i-1][j][l][1];
				}
			}
		}
	}
	ll ans=0;
	for(int i = 1; i <= _a.size(); i++)
	{
		for(int j = 0; j < 10; j++)
		{
			for(int k = 0; k < 10; k++)
			{
				for(int p = 0; p <= 2; p++)
				{
					if(i==_a.size() && p==2) continue;
					ans+=dp[i][j][k][p];
				}
			}
		}
	}
	return ans;
}

void solve()
{
	ll ans=calc(b)-calc(a);
	cout << ans;
}

int main() 
{
//	auto start_time = chrono::high_resolution_clock::now();
//	freopen("test.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    input();
    solve();
//    auto end_time = chrono::high_resolution_clock::now();
//        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
//        cout << "\n[ " << duration << " ms ]\n"; 
}

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

numbers.cpp: In function 'long long int calc(long long int)':
numbers.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 2; i <= _a.size(); i++)
      |                 ~~^~~~~~~~~~~~
numbers.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i = 1; i <= _a.size(); i++)
      |                 ~~^~~~~~~~~~~~
numbers.cpp:82:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |      if(i==_a.size() && p==2) continue;
      |         ~^~~~~~~~~~~

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