oj.uz

답안 #869011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869011 2023-11-02T23:41:08 Z bobbilyking Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 600 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN
#define M 1000000007 // 998244353

//digit dp
ll dp[20][2][13][13][2]; //also can have auxiliary info
string r;

constexpr ll INVALID = 10;

#define DP dp[pos][is_eq][l2][l1][lz]
ll solve(int pos, bool is_eq, ll l2, ll l1, ll lz) {
	if (~DP) return DP;
	if (pos==r.size())
		return DP=1;

	DP = 0;
	for (int i=0;i<=(is_eq?r[pos] - '0':9);i++){
        if (l1 == i) continue;
        if (l2 == i) continue;
        bool nlz = lz and !i;
        

        if (nlz) {
            assert(!i);
            DP += solve(pos+1, is_eq && i==r[pos] - '0', INVALID, INVALID, nlz);
        } else {    
            DP += solve(pos+1, is_eq && i==r[pos] - '0', l1, i,  nlz);
        }

        
        // if (i == 1) cout << "LOLLLLLLLL?? " << pos << " " << is_eq << " " << l2 << " " << l2 << " : " << DP << endl;
    }

	return DP;
}


int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    ll a,b;
    cin >> a >> b;
    ll lo=0;
    if (a ){
        
    memset(dp, -1, sizeof dp);
    r = to_string(a-1);
    lo = solve(0, 1, INVALID, INVALID, 1);
    }   

    // cout << "YO " << lo << endl;


    memset(dp, -1, sizeof dp);
    r = to_string(b);

    cout << solve(0, 1, INVALID, INVALID, 1)- lo << '\n';
}

Compilation message

numbers.cpp: In function 'll solve(int, bool, ll, ll, ll)':
numbers.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  if (pos==r.size())
      |      ~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
75.0 / 75.0

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