oj.uz

Submission #845923

# Submission time Handle Problem Language Result Execution time Memory
845923 2023-09-06T19:34:28 Z sofija6 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 2 ms 856 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[3][3][20][11][11],a[20],b[20];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string sa,sb;
    cin >> sa >> sb;
    for (ll i=0;i<sa.size();i++)
        a[i+1]=sa[i]-'0';
    for (ll i=0;i<sb.size();i++)
        b[i+1]=sb[i]-'0';
    for (ll i=1;i<10;i++)
    {
        ll x=i<a[1]?0 : i==a[1]?1 : 2,y=i<b[1]?0 : i==b[1]?1 : 2;
        dp[x][y][1][10][i]=1;
    }
    for (ll i=2;i<=sb.size();i++)
    {
        for (ll j=0;j<3;j++)
        {
            for (ll l=0;l<3;l++)
            {
                for (ll p=0;p<=10;p++)
                {
                    for (ll k=0;k<10;k++)
                    {
                        for (ll c=0;c<10;c++)
                        {
                            ll x,y;
                            if (i>sa.size())
                                x=2;
                            else if (j!=1)
                                x=j;
                            else
                                x=c<a[i]?0 : c==a[i]?1 : 2;
                            if (l!=1)
                                y=l;
                            else
                                y=c<b[i]?0 : c==b[i]?1 : 2;
                            if (c!=p && c!=k)
                                dp[x][y][i][k][c]+=dp[j][l][i-1][p][k];
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    for (ll i=sa.size();i<=sb.size();i++)
    {
        if (i==sa.size() && i!=sb.size())
        {
            for (ll j=0;j<=10;j++)
            {
                for (ll l=0;l<10;l++)
                {
                    for (ll k=0;k<3;k++)
                        ans+=dp[2][k][i][j][l]+dp[1][k][i][j][l];
                }
            }
            continue;
        }
        if (i==sb.size() && i!=sa.size())
        {
            for (ll j=0;j<=10;j++)
            {
                for (ll l=0;l<10;l++)
                {
                    for (ll k=0;k<3;k++)
                        ans+=dp[k][0][i][j][l]+dp[k][1][i][j][l];
                }
            }
            continue;
        }
        if (i==sa.size() && i==sb.size())
        {
            for (ll j=0;j<=10;j++)
            {
                for (ll l=0;l<10;l++)
                    ans+=dp[2][0][i][j][l]+dp[2][1][i][j][l]+dp[1][0][i][j][l]+dp[1][1][i][j][l];
            }
            continue;
        }
        for (ll j=0;j<=10;j++)
        {
            for (ll l=0;l<10;l++)
            {
                for (ll k=0;k<3;k++)
                {
                    for (ll p=0;p<3;p++)
                        ans+=dp[k][p][i][j][l];
                }
            }
        }
    }
    cout << ans+(sa=="0");
    return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:10:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (ll i=0;i<sa.size();i++)
      |                 ~^~~~~~~~~~
numbers.cpp:12:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (ll i=0;i<sb.size();i++)
      |                 ~^~~~~~~~~~
numbers.cpp:19:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (ll i=2;i<=sb.size();i++)
      |                 ~^~~~~~~~~~~
numbers.cpp:32:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                             if (i>sa.size())
      |                                 ~^~~~~~~~~~
numbers.cpp:51:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (ll i=sa.size();i<=sb.size();i++)
      |                         ~^~~~~~~~~~~
numbers.cpp:53:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if (i==sa.size() && i!=sb.size())
      |             ~^~~~~~~~~~~
numbers.cpp:53:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if (i==sa.size() && i!=sb.size())
      |                             ~^~~~~~~~~~~
numbers.cpp:65:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if (i==sb.size() && i!=sa.size())
      |             ~^~~~~~~~~~~
numbers.cpp:65:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if (i==sb.size() && i!=sa.size())
      |                             ~^~~~~~~~~~~
numbers.cpp:77:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         if (i==sa.size() && i==sb.size())
      |             ~^~~~~~~~~~~
numbers.cpp:77:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         if (i==sa.size() && i==sb.size())
      |                             ~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 400 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 472 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 464 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
75.0 / 75.0

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