oj.uz

Submission #973529

# Submission time Handle Problem Language Result Execution time Memory
973529 2024-05-02T06:45:35 Z Aiperiii Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    string a,b;
    cin>>a>>b;
    int ans=0;
    int n=a.size();
    int m=b.size();
    bool ok=1;
    for(int i=0;i<n;i++){
        if(i+1<n && a[i]==a[i+1])ok=0;
        if(i+2<n && a[i]==a[i+2])ok=0;
    }
    if(ok)ans++;
    if(a!=b){
        ok=1;
        for(int i=0;i<m;i++){
            if(i+1<m && b[i]==b[i+1])ok=0;
            if(i+2<m && b[i]==b[i+2])ok=0;
        }
        if(ok)ans++;
    }
  //  cout<<ans<<"\n";
    for(int i=n+1;i<m;i++){
        int cnt=1;
        for(int j=0;j<i;j++){
            if(j<=1)cnt*=9;
            else cnt*=8;
        }
        ans+=cnt;
    }
   // cout<<ans<<"\n";
    if(n<m){
        int s=1;
        string st=a;
        for(int i=n-1;i>=0;i--){
            st.pop_back();
            bool ok=1;
            for(int j=0;j<st.size();j++){
                if(j+1<st.size() && st[j]==st[j+1])ok=0;
                if(j+2<st.size() && st[j]==st[j+2])ok=0;
            }
            if(ok){
                for(char x=a[i];x<='9';x++){
                    if(x==a[i])continue;
                    if(i-1>=0 && x==a[i-1])continue;
                    if(i-2>=0 && x==a[i-2])continue;
                    ans+=s;
                }
            }
            
            if(i>1)s*=8;
            else s*=9;
        }
        s=1;
        st=b;
        for(int i=m-1;i>=0;i--){
            st.pop_back();
            bool ok=1;
            for(int j=0;j<st.size();j++){
                if(j+1<st.size() && st[j]==st[j+1])ok=0;
                if(j+2<st.size() && st[j]==st[j+2])ok=0;
            }
            if(ok){
                char c='0';
                if(i==0)c='1';
                for(char x=b[i];x>=c;x--){
                    if(x==b[i])continue;
                    if(i-1>=0 && x==b[i-1])continue;
                    if(i-2>=0 && x==b[i-2])continue;
                    ans+=s;
                }
            }
            if(i>1)s*=8;
            else s*=9;
        }
    }
    else if(a!=b){
        int ind=n-1;
        for(int i=0;i<n;i++){
            if(b[i]>a[i]){
                ind=i;break;
            }
        }
        
        int s=1;
        string st=a;
        for(int i=n-1;i>=0;i--){
            st.pop_back();
            bool ok=1;
            for(int j=0;j<st.size();j++){
                if(j+1<st.size() && st[j]==st[j+1])ok=0;
                if(j+2<st.size() && st[j]==st[j+2])ok=0;
            }
            if(i<ind)break;
            if(ok){
                char c='9';
                if(i==ind){
                    c=b[i];
                    c--;
                }
                for(char x=a[i];x<=c;x++){
                    if(x==a[i])continue;
                    if(i-1>=0 && x==a[i-1])continue;
                    if(i-2>=0 && x==a[i-2])continue;
                    ans+=s;
                }
            }
            
            if(i>1)s*=8;
            else s*=9;
        }
        
        s=1;
        st=b;
        for(int i=m-1;i>=0;i--){
            st.pop_back();
            bool ok=1;
            for(int j=0;j<st.size();j++){
                if(j+1<st.size() && st[j]==st[j+1])ok=0;
                if(j+2<st.size() && st[j]==st[j+2])ok=0;
            }
            if(i==ind)break;
            if(ok){
                char c='0';
                for(char x=b[i];x>=c;x--){
                    if(x==b[i])continue;
                    if(i-1>=0 && x==b[i-1])continue;
                    if(i-2>=0 && x==b[i-2])continue;
                    ans+=s;
                }
            }
            if(i>1)s*=8;
            else s*=9;
        }
    }
    cout<<ans<<"\n";
}
/*
123 321
123456789 987654321
*/

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:46: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]
   46 |             for(int j=0;j<st.size();j++){
      |                         ~^~~~~~~~~~
numbers.cpp:47:23: 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]
   47 |                 if(j+1<st.size() && st[j]==st[j+1])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:48:23: 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]
   48 |                 if(j+2<st.size() && st[j]==st[j+2])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:67: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]
   67 |             for(int j=0;j<st.size();j++){
      |                         ~^~~~~~~~~~
numbers.cpp:68:23: 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]
   68 |                 if(j+1<st.size() && st[j]==st[j+1])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:69:23: 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]
   69 |                 if(j+2<st.size() && st[j]==st[j+2])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:98: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]
   98 |             for(int j=0;j<st.size();j++){
      |                         ~^~~~~~~~~~
numbers.cpp:99:23: 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]
   99 |                 if(j+1<st.size() && st[j]==st[j+1])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:100:23: 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]
  100 |                 if(j+2<st.size() && st[j]==st[j+2])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:126: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]
  126 |             for(int j=0;j<st.size();j++){
      |                         ~^~~~~~~~~~
numbers.cpp:127:23: 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]
  127 |                 if(j+1<st.size() && st[j]==st[j+1])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:128:23: 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]
  128 |                 if(j+2<st.size() && st[j]==st[j+2])ok=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 344 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 348 KB Output is correct
6 Correct 0 ms 344 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 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct

Subtask #2
75.0 / 75.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 1 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 344 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 344 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 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 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 536 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 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 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct