제출 #845923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845923		sofija6	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	856 KiB

numbers

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 25
• Subtask 2: 75 / 75