oj.uz

Submission #49008

# Submission time Handle Problem Language Result Execution time Memory
49008 2018-05-21T06:43:57 Z Namnamseo Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 4 ms 1008 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

char s[50];
int sn;

ll f(ll x){
	sprintf(s, "%lld", x);
	for(sn=0; s[sn]; ++sn);
	ll ans = 0;
	for(int i=0; i<sn; ++i){
		int t = s[i]-'0';
		for(int j=0; j<t; ++j){
			if(i>=1 && s[i-1]-'0' == j) continue;
			if(i>=2 && s[i-2]-'0' == j) continue;
			if(i==0 && j==0){
				ll curS=0;
				for(int a=1; a<=sn; ++a){
					ll cur=1;
					for(int b=a; b<sn; ++b){
						if(b<=a+1) cur *= 9;
						else cur *= 8;
					}
					curS += cur;
				}
				ans += curS;
				continue;
			}
			ll cur=1;
			for(int k=i+1; k<sn; ++k){
				if(k == 1){
					cur *= 9;
				}
				else {
					cur *= 8;
				}
			}
			ans += cur;
		}
		if(i>=1 && s[i-1]==s[i]){
			break;
		}
		if(i>=2 && s[i-2]==s[i]){
			break;
		}
		if(i == sn-1) ++ans;
	}
	for(int i=0; i<sn; ++i) s[i]=0;
	return ans;
}

int main(){
	ll a,b;
	read(a,b);
	ll ans = f(b);
	if(a) ans -= f(a-1);
	printf("%lld\n", ans);
	return 0;
}

Compilation message

numbers.cpp: In function 'void read(int&)':
numbers.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
numbers.cpp: In function 'void read(ll&)':
numbers.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 920 KB Output is correct
2 Correct 2 ms 920 KB Output is correct
3 Correct 2 ms 920 KB Output is correct
4 Correct 2 ms 936 KB Output is correct
5 Correct 3 ms 936 KB Output is correct
6 Correct 2 ms 936 KB Output is correct
7 Correct 2 ms 936 KB Output is correct
8 Correct 2 ms 936 KB Output is correct
9 Correct 2 ms 936 KB Output is correct
10 Correct 2 ms 936 KB Output is correct
11 Correct 2 ms 936 KB Output is correct
12 Correct 2 ms 936 KB Output is correct
13 Correct 4 ms 936 KB Output is correct
14 Correct 2 ms 936 KB Output is correct
15 Correct 2 ms 936 KB Output is correct
16 Correct 2 ms 936 KB Output is correct
17 Correct 2 ms 936 KB Output is correct
18 Correct 2 ms 936 KB Output is correct
19 Correct 3 ms 936 KB Output is correct
20 Correct 2 ms 936 KB Output is correct
21 Correct 2 ms 936 KB Output is correct
22 Correct 3 ms 936 KB Output is correct
23 Correct 2 ms 936 KB Output is correct
24 Correct 2 ms 936 KB Output is correct
25 Correct 2 ms 936 KB Output is correct
26 Correct 2 ms 936 KB Output is correct
27 Correct 4 ms 936 KB Output is correct
28 Correct 2 ms 936 KB Output is correct
29 Correct 2 ms 940 KB Output is correct
30 Correct 2 ms 944 KB Output is correct
31 Correct 2 ms 952 KB Output is correct
32 Correct 3 ms 952 KB Output is correct
33 Correct 3 ms 960 KB Output is correct
34 Correct 3 ms 960 KB Output is correct
35 Correct 3 ms 960 KB Output is correct
36 Correct 2 ms 964 KB Output is correct
37 Correct 2 ms 968 KB Output is correct
38 Correct 2 ms 972 KB Output is correct
39 Correct 2 ms 976 KB Output is correct
40 Correct 2 ms 980 KB Output is correct
41 Correct 2 ms 984 KB Output is correct
42 Correct 2 ms 988 KB Output is correct
43 Correct 2 ms 1000 KB Output is correct
44 Correct 3 ms 1000 KB Output is correct
45 Correct 3 ms 1008 KB Output is correct