oj.uz

Submission #126049

# Submission time Handle Problem Language Result Execution time Memory
126049 2019-07-06T21:04:36 Z wasyl Palindrome-Free Numbers (BOI13_numbers) C++11
100 / 100
 2 ms 504 KB 
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #ifndef DEBUG
    #define d(...)
    #else
    #define d(...) cerr << "\033[36m" << __VA_ARGS__ << "\033[0m"
    #endif
    #define R resize
    #define EB emplace_back
    #define LOG(x) #x << ": " << x
    #define ALL(x) (x).begin(), (x).end()
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
     
    ll a, b;
     
    ll mypow ( int n, int wyk )
    {
        if ( wyk == 0 )
            return 1;
        if ( wyk == 1 )
            return n;
        if ( wyk & 1 )
            return (ll)n * mypow( n, wyk - 1 );
        ll tmp = mypow( n, wyk / 2 );
        return tmp * tmp;
    }
     
    ll licz ( int prz, int poz )
    {
        d( "licz: " << prz << ' ' << poz );
        ll res = 1;
        if ( prz < 2 and poz )
            res *= 9, --poz;
        res *= mypow( 8, poz );
        d( ' ' << res << ' ' );
        return res;
    }
     
    ll foo ( ll n )
    {
        if ( n == -1 )
            return 0;
        ll res = 1;
        string s = to_string( n );
        d( s << '\n' );
        for ( int i = 1; i <= s.size() - 1; ++i )
            res += mypow( 9, min( 2, i ) ) * mypow( 8, max( 0, i - 2 ) );
        d( "po pierwszym dodaniu " << res << '\n' );
        int i = 0;
        for ( ; i < s.size(); ++i )
        {
            int p = s[i] - '0' - 1;
            int il = s[i] - '0';
            if ( i == 0 )
                --il;
            if ( i - 2 >= 0 and s[i - 2] - '0' <= p )
                --il;
            if ( i - 1 >= 0 and s[i - 1] - '0' <= p )
                --il;
            d( LOG( i ) << ' ' << LOG( p ) << ' ' << LOG( il ) << '\n' );
            ll dod = (ll)il * licz( min( 2, i + 1 ), (int)s.size() - i - 1 );
            d( dod << '\n' );
            res += dod;
            if ( i - 2 >= 0 and s[i - 2] == s[i] )
                break;
            if ( i - 1 >= 0 and s[i - 1] == s[i] )
                break; 
        }
        if ( i == s.size() ) 
            ++res;
        d( "res na koncu " << res << '\n' );
        return res;
    }   
     
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cin >> a >> b;
        cout << foo( b ) - foo( a - 1 ) << '\n';
    }

Compilation message

numbers.cpp: In function 'll foo(ll)':
numbers.cpp:49:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( int i = 1; i <= s.size() - 1; ++i )
                          ~~^~~~~~~~~~~~~~~
numbers.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( ; i < s.size(); ++i )
                 ~~^~~~~~~~~~
numbers.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ( i == s.size() ) 
              ~~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 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 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 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 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 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 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 2 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 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 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 2 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 2 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 252 KB Output is correct
27 Correct 2 ms 376 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 2 ms 380 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 376 KB Output is correct
45 Correct 2 ms 376 KB Output is correct