oj.uz

답안 #51539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51539 2018-06-18T08:22:39 Z WA_TLE Palindrome-Free Numbers (BOI13_numbers) C++14
73.75 / 100
 4 ms 748 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
llint solve(llint in){
	
	if(in==0){return 0;}
	array<llint,100>dp={0};
	llint keta[22]={0};
	for(llint h=0;h<22;h++){keta[h]=in%10;in/=10;}
	bool paf=true;//ここまでparindrome-freeですか?
	llint h=21,i,j;
	while(keta[h]==0){h--;}
	llint turn=0;
	for(;h>=0;h--){
		array<llint,100>ddp={0};
		for(i=0;i<100;i++){//繊維元
			for(j=0;j<10;j++){//繊維先
				if(i%10==j||((turn>1)&&(i/10==j))){continue;}//だめ
				ddp[(i%10)*10 +j]+=dp[i];
				
			}
		}
		if(paf){
			llint mae=keta[h+2]*10+keta[h+1];
			for(j=0;j<keta[h];j++){
				if(turn==0&&j==0){continue;}
				if(turn==1){mae+=100;}
				if(mae/10==j||mae%10==j){continue;}//だめ
				ddp[(mae%10)*10 +j]++;
			}
		}
		if(keta[h+1]==keta[h]||(turn>1&&keta[h+2]==keta[h])){paf=false;}
		dp=ddp;
		dp[0]++;
		turn++;
	}
	llint ans=0;
	for(i=0;i<100;i++){ans+=dp[i];}
	return ans;
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	llint a,b;cin>>a>>b;
	cout<<solve(b+1)-solve(a)<<endl;
	return 0;
}

Subtask #1
13.75 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 460 KB Output isn't correct
3 Correct 2 ms 460 KB Output is correct
4 Incorrect 2 ms 460 KB Output isn't correct
5 Correct 3 ms 460 KB Output is correct
6 Incorrect 3 ms 460 KB Output isn't correct
7 Incorrect 3 ms 460 KB Output isn't correct
8 Incorrect 2 ms 536 KB Output isn't correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 624 KB Output is correct
12 Correct 2 ms 672 KB Output is correct
13 Correct 3 ms 672 KB Output is correct
14 Incorrect 3 ms 672 KB Output isn't correct
15 Incorrect 2 ms 700 KB Output isn't correct
16 Correct 2 ms 700 KB Output is correct
17 Correct 3 ms 700 KB Output is correct
18 Correct 2 ms 700 KB Output is correct
19 Correct 2 ms 700 KB Output is correct
20 Incorrect 3 ms 724 KB Output isn't correct

Subtask #2
60.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Incorrect 3 ms 732 KB Output isn't correct
6 Correct 2 ms 732 KB Output is correct
7 Incorrect 3 ms 732 KB Output isn't correct
8 Incorrect 2 ms 732 KB Output isn't correct
9 Incorrect 3 ms 732 KB Output isn't correct
10 Incorrect 2 ms 732 KB Output isn't correct
11 Correct 2 ms 732 KB Output is correct
12 Incorrect 2 ms 732 KB Output isn't correct
13 Incorrect 2 ms 732 KB Output isn't correct
14 Incorrect 2 ms 732 KB Output isn't correct
15 Incorrect 2 ms 732 KB Output isn't correct
16 Correct 2 ms 732 KB Output is correct
17 Correct 2 ms 732 KB Output is correct
18 Correct 2 ms 732 KB Output is correct
19 Correct 2 ms 732 KB Output is correct
20 Correct 2 ms 732 KB Output is correct
21 Correct 3 ms 732 KB Output is correct
22 Correct 2 ms 732 KB Output is correct
23 Correct 3 ms 732 KB Output is correct
24 Correct 2 ms 732 KB Output is correct
25 Correct 2 ms 732 KB Output is correct
26 Correct 2 ms 732 KB Output is correct
27 Correct 2 ms 740 KB Output is correct
28 Correct 2 ms 740 KB Output is correct
29 Correct 2 ms 740 KB Output is correct
30 Correct 2 ms 748 KB Output is correct
31 Correct 2 ms 748 KB Output is correct
32 Correct 2 ms 748 KB Output is correct
33 Correct 2 ms 748 KB Output is correct
34 Correct 2 ms 748 KB Output is correct
35 Correct 4 ms 748 KB Output is correct
36 Correct 3 ms 748 KB Output is correct
37 Correct 2 ms 748 KB Output is correct
38 Correct 2 ms 748 KB Output is correct
39 Correct 2 ms 748 KB Output is correct
40 Correct 2 ms 748 KB Output is correct
41 Correct 3 ms 748 KB Output is correct
42 Correct 2 ms 748 KB Output is correct
43 Correct 2 ms 748 KB Output is correct
44 Correct 2 ms 748 KB Output is correct
45 Correct 2 ms 748 KB Output is correct