oj.uz

Submission #973520

# Submission time Handle Problem Language Result Execution time Memory
973520 2024-05-02T06:30:05 Z Aiperiii Palindrome-Free Numbers (BOI13_numbers) C++14
80 / 100
 1 ms 848 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++;
    }

    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;
    }
  
    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(ok){
                char c='9';
                if(i==ind){
                    c=b[i];
                    c--;
                }
                else if(i<ind)break;
                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(ok){
                char c='0';
                if(i==ind)break;
                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:99: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]
   99 |             for(int j=0;j<st.size();j++){
      |                         ~^~~~~~~~~~
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+1<st.size() && st[j]==st[j+1])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:101: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]
  101 |                 if(j+2<st.size() && st[j]==st[j+2])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:127: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]
  127 |             for(int j=0;j<st.size();j++){
      |                         ~^~~~~~~~~~
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+1<st.size() && st[j]==st[j+1])ok=0;
      |                    ~~~^~~~~~~~~~
numbers.cpp:129: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]
  129 |                 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 436 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 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 440 KB Output is correct
12 Correct 0 ms 440 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 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 600 KB Output is correct

Subtask #2
55.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 432 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 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Incorrect 0 ms 432 KB Output isn't correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Correct 1 ms 344 KB Output is correct
22 Incorrect 1 ms 348 KB Output isn't correct
23 Correct 1 ms 348 KB Output is correct
24 Incorrect 0 ms 440 KB Output isn't correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 436 KB Output is correct
28 Correct 1 ms 848 KB Output is correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Incorrect 0 ms 348 KB Output isn't correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Correct 0 ms 348 KB Output is correct
34 Incorrect 0 ms 348 KB Output isn't correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Incorrect 0 ms 348 KB Output isn't correct
41 Correct 0 ms 348 KB Output is correct
42 Incorrect 0 ms 348 KB Output isn't correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct