oj.uz

Submission #58570

# Submission time Handle Problem Language Result Execution time Memory
58570 2018-07-18T08:27:29 Z Batrr Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 4 ms 636 KB 
#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=2e5+123,inf=1e18,mod=1e9+7,N=360360,LOG=20;
ll a,b,ans;
vector<int> av,bv;
vector<int> tov(ll x){
    vector<int> res;
    if(x==0)
        res.pb(0);
    while(x){
        res.pb(x%10);
        x/=10;
    }
    reverse(res.begin(),res.end());
    return res;
}
ll calc(int a,int b,int len){
    if(len==0)
        return 1;
    ll res=1;
    if(b==-1)
        res=9,len--;    
    while(len--)
        res*=8;
    return res;
}
ll get(vector<int> s){
    if(s.size()==1)
        return s[0]+1;
    ll res=0;
    for(int i=1;i<s.size();i++){
        if(i==1)
            res+=10;
        else
            res+=9*9*pow(8,i-2);
    }
    for(int i=0;i<s.size();i++){
        //cout<<i<<" "<<s.size()<<endl;
        int a,b,c;
        a=b=-1;
        if(i>1)
            a=s[i-2];
        if(i>0)
            b=s[i-1];
        for(int j=(i==0);j<s[i];j++){
            c=j;
            if(a==c || b==c)
                continue;
    //        cout<<a<<" "<<b<<" "<<c<<" "<<i<<" "<<endl;
            res+=calc(a,b,s.size()-1-i);
        }
        if(i>0 && s[i]==s[i-1])
            break;
        if(i>1 && s[i]==s[i-2])
            break;
        if(i==s.size()-1)
            res++;
    }    
    return res;
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif                                     
    cin>>a>>b;   
    av=tov(a-1);
    bv=tov(b);
    cout<<get(bv)-get(av);
}

Compilation message

numbers.cpp: In function 'long long int get(std::vector<int>)':
numbers.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<s.size();i++){
                 ~^~~~~~~~~
numbers.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
numbers.cpp:69:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==s.size()-1)
            ~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 3 ms 432 KB Output is correct
6 Correct 2 ms 432 KB Output is correct
7 Correct 3 ms 432 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 3 ms 636 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 636 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 636 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 3 ms 636 KB Output is correct
18 Correct 2 ms 636 KB Output is correct
19 Correct 2 ms 636 KB Output is correct
20 Correct 3 ms 636 KB Output is correct

Subtask #2
75.0 / 75.0

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