oj.uz

Submission #1078440

# Submission time Handle Problem Language Result Execution time Memory
1078440 2024-08-27T17:25:02 Z modwwe Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 484 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e9;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid;
int  i,s10,s12;
int kk;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
//fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    //modwwe
 phongbeo();
//checktime
}
int dp[18][2][10][10];
vector<int> v;
int calc(int a,bool b,int x,int y)
{
    if(a==v.size()) return 1;
    if(dp[a][b][x][y]!=-1) return dp[a][b][x][y];
    int& s=dp[a][b][x][y];
    s=0;
    int limit=v[a];
    if(b)limit=9;
    if(x==y)
    {
        if(a==v.size()-1&&b) {
                return s=10;}
        else if(a==v.size()-1&&!b) return s=v[a]+1;
        else if(b)
        {
            for(int i=1; i<=9; i++)
                for(int j=0; j<=9; j++)
                {
                    if(i==j) continue;
                    s+=calc(a+2,1,i,j);
                }
                s+=calc(a+1,b,0,0);
        }
        else
        {
            for(int i=v[a]; i>=1; i--)
            {
                int llimit=v[a+1];
                if(i!=v[a])llimit=9,b=1;
                for(int j=0; j<=llimit; j++)
                { if(i==j) continue;
                    if(llimit==j)s+=calc(a+2,b,i,j);
                    else s+=calc(a+2,1,i,j);
                }
            }
            if(v[a]==0)s+=calc(a+1,b,0,0);
            else s+=calc(a+1,1,0,0);
        }
    }
    else
    {
        for(int i=0; i<=limit; i++)
        {
            if(i==x||i==y) continue;
             if(i==limit)s+=calc(a+1,b,y,i);
             else s+=calc(a+1,1,y,i);
        }
    }
    return s;
}
#define getchar_unlocked getchar

inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
int get(int x)
{
    v.clear();
    while(x!=0)
    {
        v.pb(x%10);
        x/=10;
    }
    reverse(v.begin(),v.end());
memset(dp,-1,sizeof dp);
    return calc(0,0,0,0);
}
void phongbeo()
{
l=scan();
r=scan();
     cout<<get(r)-get(l-1);
}

Compilation message

numbers.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
numbers.cpp: In function 'long long int calc(long long int, bool, long long int, long long int)':
numbers.cpp:64:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(a==v.size()) return 1;
      |        ~^~~~~~~~~~
numbers.cpp:72:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(a==v.size()-1&&b) {
      |            ~^~~~~~~~~~~~
numbers.cpp:74:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         else if(a==v.size()-1&&!b) return s=v[a]+1;
      |                 ~^~~~~~~~~~~~
numbers.cpp:77:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   77 |             for(int i=1; i<=9; i++)
      |             ^~~
numbers.cpp:83:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   83 |                 s+=calc(a+1,b,0,0);
      |                 ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 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 0 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 344 KB Output is correct
13 Correct 1 ms 348 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 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 1 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 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 1 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
21 Correct 0 ms 484 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 356 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 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 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 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct