Submission #158417

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
158417	2019-10-17T02:59:48 Z	junodeveloper	Palindrome-Free Numbers (BOI13_numbers)	C++14	92.5 / 100	3 ms	424 KB

numbers

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll N,dp[20][11][11][2],pw[20];
ll go(int pos,int pre, int cur, int eql) {
	if(pos==0) return 1;
	ll& ret=dp[pos][pre][cur][eql];
	if(ret!=-1) return ret;
	ret=0;
	int i,j=N/pw[pos-1]%10;
	if(eql) {
		if(j!=pre && j!=cur)
			ret+=go(pos-1, cur, j, eql);
	}
	for(i=0;i<(eql?j:10);i++) {
		if(i==pre || i==cur) continue;
		ret+=go(pos-1,cur,i,0);
	}
	return ret;
}
ll f(ll n) {
	N=n;
	memset(dp,-1,sizeof(dp));
	ll v=1; int pos=0;
	while(n/v>=10) v*=10, pos++;
	ll ret=0;
	int i,j;
	for(i=pos;i>=0;i--) {
		if(i==pos) ret+=go(i,10,n/v%10,1);
		for(j=1;j<(i==pos?n/v%10:10);j++)
			ret+=go(i,10,j,0);
	}
	return ret;
}
int main() {
	int i;
	pw[0]=1;
	for(i=1;i<20;i++) pw[i]=10*pw[i-1];
	ll a,b;
	scanf("%lld%lld",&a,&b);
	printf("%lld",f(b)-f(a-1));
	return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

17.5 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Incorrect	2 ms	396 KB	Output isn't correct
5	Incorrect	2 ms	376 KB	Output isn't correct
6	Incorrect	2 ms	376 KB	Output isn't correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	380 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Incorrect	2 ms	380 KB	Output isn't correct
15	Incorrect	2 ms	376 KB	Output isn't correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Incorrect	2 ms	376 KB	Output isn't correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	380 KB	Output is correct

Subtask #2

75.0 / 75.0

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