oj.uz

Submission #653989

# Submission time Handle Problem Language Result Execution time Memory
653989 2022-10-29T08:57:47 Z keitherrrr Palindrome-Free Numbers (BOI13_numbers) C++17
73.75 / 100
 1 ms 416 KB 
   #include <bits/stdc++.h>
                using namespace std;
 
                #define int long long 
                #define all(x) x.begin(), x.end()
                #define ll long long
                #define mp make_pair
                #define pb push_back
                #define pii pair <int, int>
                #define vi vector<int>
                
                #define FOR(i, a, b) for (int i=a; i<b; i++)
                #define FORd(i, a, b) for (int i=a-1; i>=b; i--)
                #define F0R(i, a) for (int i=0; i<a; i++)
                
        #define fi first
        #define se second
        #define be begin
        #define e end
        #define lb lower_bound
        #define ub upper_bound 
        #define db long double
        #define mid ((r+l)>>1)
        #define tl (id<<1)
        #define tr (id<<1|1)
const int N=20;
vi v;
int f[20][11][11][2],   n;  
int dp(int i,int val,int oldval,bool tight){
    if(i>=n) return 1;  
    int &res=f[i][val][oldval][tight]; 
    if(res!=-1) return res; 
    res=0;  
    int limit=(tight)?v[i]:9;  
    for(int d=0;d<=limit;d++)
        if(d!=oldval&&d!=val){
            int cur;  
            if(i==0&&d==0) cur=10;  
            else cur=d; 
            res+= dp(i+1,cur,val,tight&&d==limit); 
        }
    return res; 
}    
int solve(string a){
    v.clear();  
    memset(f,-1,sizeof(f));  
    FOR(i,0,a.size()) v.pb(a[i]-'0');
    n=v.size();    
    return dp(0,10,10,1);  
}      
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    string a,b; cin >>a>>b;  
    int ans=solve(b)-solve(a);  
    bool g=0;  
    FOR(i,2,a.size()) if(a[i]==a[i-2]||a[i]==a[i-1]) {g=1; break;}
    if(!g) ans++;
    cout<<ans; 
}

Compilation message

numbers.cpp: In function 'long long int solve(std::string)':
numbers.cpp:12:53: 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 |                 #define FOR(i, a, b) for (int i=a; i<b; i++)
......
   47 |     FOR(i,0,a.size()) v.pb(a[i]-'0');
      |         ~~~~~~~~~~~~                                 
numbers.cpp:47:5: note: in expansion of macro 'FOR'
   47 |     FOR(i,0,a.size()) v.pb(a[i]-'0');
      |     ^~~
numbers.cpp: At global scope:
numbers.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~
numbers.cpp: In function 'int main()':
numbers.cpp:12:53: 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 |                 #define FOR(i, a, b) for (int i=a; i<b; i++)
......
   56 |     FOR(i,2,a.size()) if(a[i]==a[i-2]||a[i]==a[i-1]) {g=1; break;}
      |         ~~~~~~~~~~~~                                 
numbers.cpp:56:5: note: in expansion of macro 'FOR'
   56 |     FOR(i,2,a.size()) if(a[i]==a[i-2]||a[i]==a[i-1]) {g=1; break;}
      |     ^~~

Subtask #1
13.75 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Incorrect 0 ms 340 KB Output isn't correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Incorrect 0 ms 340 KB Output isn't correct

Subtask #2
60.0 / 75.0

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