oj.uz

Submission #860111

# Submission time Handle Problem Language Result Execution time Memory
860111 2023-10-11T16:28:43 Z Ellinor Palindrome-Free Numbers (BOI13_numbers) C++14
62.9167 / 100
 1 ms 504 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <cstdlib>
#include <set>
#include <iomanip>
#include <limits>
#include <map>
#include <assert.h>
#include <algorithm>
#include <list>
#include <iterator>
#include <fstream>
#include <random>
#include <unordered_map>
#include <array>
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

//

ll a, b;

vector<int> digits;

vector<vector<vector<vector<ll>>>> dp;


void digify(ll number)
{
    digits.clear();

    while(number > 0)
    {
        digits.push_back(number % 10); //push the last digit in
        number /= 10; //truncate the digit
    }
    reverse(digits.begin(), digits.end());
}


// int GetNumberOfDigits (ll i)
// {
//     return i > 0 ? (int) log10 ((double) i) + 1 : 1;
// }


ll rec(int at, bool edgy, int d2, int d1)
{
    if (at == digits.size()) return 1;

    if (dp[at][edgy][d2 == -1 ? 10 : d2][d1 == -1 ? 10 : d1] != -1) return dp[at][edgy][d2][d1];

    ll ret = 0;
    rep(d,0, edgy ? digits[at] + 1 : 10)
    {
        if (d == d2 || d == d1) continue;

        bool new_edgy = edgy && (d == digits[at]);
        bool leading_zero = d1 == -1 && d == 0;

        ret += rec(at + 1, new_edgy, d1, leading_zero ? -1 : d);
    }

    dp[at][edgy][d2 == -1 ? 10 : d2][d1 == -1 ? 10 : d1] = ret;
    return ret;
}

int32_t main()
{
    // cerr << "hi :) ";
    fast();
    cin >> a >> b;

    digify(a - 1);

    dp.assign(digits.size(), vector<vector<vector<ll>>>(2, vector<vector<ll>>(11, vector<ll>(11, -1))));
    int aans = rec(0, true, -1, -1); // a-1

    // cerr << aans << "\n";
    
    digify(b);
    dp.assign(digits.size(), vector<vector<vector<ll>>>(2, vector<vector<ll>>(11, vector<ll>(11, -1))));
    int bans = rec(0, true, -1, -1); // b

    // cerr << bans << "\n";

    ll ans = bans - aans;
    cout << ans << "\n";
}

Compilation message

numbers.cpp: In function 'll rec(int, bool, int, int)':
numbers.cpp:71:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     if (at == digits.size()) return 1;
      |         ~~~^~~~~~~~~~~~~~~~

Subtask #1
21.25 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 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 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #2
41.6666666667 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 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 0 ms 348 KB Output is correct
15 Correct 0 ms 492 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 504 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Correct 0 ms 348 KB Output is correct
23 Incorrect 0 ms 348 KB Output isn't correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 0 ms 348 KB Output isn't correct
26 Incorrect 0 ms 348 KB Output isn't correct
27 Incorrect 0 ms 348 KB Output isn't correct
28 Incorrect 0 ms 348 KB Output isn't correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Incorrect 0 ms 348 KB Output isn't correct
32 Correct 0 ms 348 KB Output is correct
33 Incorrect 0 ms 348 KB Output isn't correct
34 Correct 0 ms 348 KB Output is correct
35 Incorrect 0 ms 348 KB Output isn't correct
36 Incorrect 0 ms 344 KB Output isn't correct
37 Incorrect 0 ms 348 KB Output isn't correct
38 Incorrect 1 ms 348 KB Output isn't correct
39 Incorrect 0 ms 348 KB Output isn't correct
40 Correct 0 ms 348 KB Output is correct
41 Incorrect 0 ms 348 KB Output isn't correct
42 Correct 0 ms 348 KB Output is correct
43 Incorrect 1 ms 344 KB Output isn't correct
44 Incorrect 1 ms 344 KB Output isn't correct
45 Incorrect 0 ms 348 KB Output isn't correct