Submission #518051

#	Time	Username	Problem	Language	Result	Execution time	Memory
518051		Ai7081	Palindrome-Free Numbers (BOI13_numbers)	C++17	45.83 / 100	1 ms	344 KiB

numbers

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

long a, b, pow8[20];

long round(long x, long k) {
    x /= pow(10, k);
    return x * pow(10, k);
}

bool check(long x) {
    long p = -1, q = -1;
    while (x > 0) {
        if (x%10 == p || x%10 == q) return false;
        q = p;
        p = x%10;
        x /= 10;
    }
    return true;
}

long all(long x, long y, long k) {
    if (!check(x/10)) return 0;
    long unit[3];
    for (int i=0; i<3; i++) {
        unit[i] = y%10;
        y /= 10;
    }
    if (!k) return (unit[0] - (unit[0] > unit[1] && (unit[1] || unit[2])) - (unit[0] > unit[2] && unit[2])) + (unit[0]!=unit[1] && unit[0]!=unit[2]);
    return (unit[0] - (unit[0] > unit[1] && (unit[1] || unit[2])) - (unit[0] > unit[2] && unit[2])) * pow8[k-1] * (8 + !(unit[2] + unit[1]));
}

long sol(long a, long b) {
    if (a > b)  return 0;
    if (a == b) return check(a);
    if (a < 10 && b < 10) return b-a+1;
    long unit_a = 0, unit_b = 0;
    while (pow(10, unit_a) <= a) unit_a++;
    while (pow(10, unit_b) <= b) unit_b++;

    if (unit_a == unit_b && round(a, unit_a-1) == round(b, unit_b-1)) {
        long ret = 0, i = 0;
        while (b != a) {
            ret += all(round(b, 1), b, i);
            a /= 10;
            b /= 10;
            i++;
        }
        return ret;
    }

    long ra = round(a, unit_b-1);
    long rb = round(b, unit_b-1);
    long ret = sol(ra, rb-1) - sol(ra, a) + check(a) + sol(rb, b);
    return ret;
}

int main() {
    pow8[0] = 1;
    for (int i=1; i<=18; i++) pow8[i] = pow8[i-1] * 8;
    scanf(" %lld %lld", &a, &b);
    printf("%lld", sol(a, b));
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf(" %lld %lld", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17.5 / 25
• Subtask 2: 28.333333333333332 / 75