Submission #633662

#	Time	Username	Problem	Language	Result	Execution time	Memory
633662		glome	Palindrome-Free Numbers (BOI13_numbers)	C++17	72.50 / 100	81 ms	380 KiB

numbers

#include <bits/stdc++.h>
 
using namespace std;

long long dp[19][200][2];

long long mod =1e9 + 7;

string num;

int pal(string n) {
    string y = n;
    reverse(y.begin(), y.end());
    return y == n;
}

int isok(string s) {
    int sig = s.size();
    for (int i = 0; i<s.size(); i++) {
        if(s[i] != '0') {
            sig = i;
            break;
        }
    }
    sig = 0;
    for (int i = sig; i<s.size(); i++) {
        string n = string(1, s[i]);
        for (int j = i + 1; j<s.size(); j++) {
            n += string(1, s[j]);
            if(pal(n)) return 0;
        }
    }
    return 1;
}

long long solve(int pos, long long cnt, int f,string s) {
    if(!isok(s)) return 0;
    if(pos == num.size()) {
        return isok(s);
    }
    if(dp[pos][cnt][f] != -1) return dp[pos][cnt][f];
    int lim = 9;
    if(!f) lim = num[pos] - '0'; 
    long long res = 0;
    for (int i = 0; i<=lim; i++) {
        res += solve(pos + 1, cnt + i, (i < lim || f), s + to_string(i));
    }
    return dp[pos][cnt][f] = res;
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    long long l, r;
    cin >> l >> r; 
    l--;
    num = to_string(l);
    memset(dp, -1, sizeof(dp));
    long long a1 = solve(0, 0, 0, "");
    memset(dp, -1, sizeof(dp));
    num = to_string(r);
    cout << solve(0, 0, 0, "") - a1 << '\n';
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'int isok(std::string)':
numbers.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i<s.size(); i++) {
      |                     ~^~~~~~~~~
numbers.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = sig; i<s.size(); i++) {
      |                       ~^~~~~~~~~
numbers.cpp:28:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int j = i + 1; j<s.size(); j++) {
      |                             ~^~~~~~~~~
numbers.cpp: In function 'long long int solve(int, long long int, int, std::string)':
numbers.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     if(pos == num.size()) {
      |        ~~~~^~~~~~~~~~~~~

• Subtask 1: 12.5 / 25
• Subtask 2: 60 / 75