제출 #518225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518225		Ai7081	Palindrome-Free Numbers (BOI13_numbers)	C++17	59.58 / 100	1 ms	364 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define long long long
const bool debug = 0;

long a, b, pow8[20], dp[20][15][15], d[20][15], sum[20][15];

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 hello(long a, long b) {
    long ret = 0, i = 0;
    while (b != a) {
        ret += all(round(b, 1), b, i);
        a /= 10;
        b /= 10;
        i++;
    }
    return ret;
}

long sol(long a, long b) {
    a--;
    long unit_a = 0, unit_b = 0;
    while (pow(10, unit_a) <= a) unit_a++;
    while (pow(10, unit_b) <= b) unit_b++;
    long ra = round(a, unit_a-1);
    long rb = round(b, unit_b-1);
    long ret = hello(rb, b) - hello(ra, a);
    long ura = 0, urb = 0;
    while (pow(10, ura) <= ra-1) ura++;
    while (pow(10, urb) <= rb-1) urb++;
    ret += sum[urb][int((rb-1) / pow(10, urb-1))];
    ret -= sum[ura][int((ra-1) / pow(10, ura-1))];
    //cout << rb << ' ' << ra << endl;
    //cout << hello(rb, b) << ' ' << hello(ra, a) << ' ' << sum[urb][int((rb-1) / pow(10, urb-1))] << ' ' << sum[ura][int((ra-1) / pow(10, ura-1))] << endl;
    return ret;
}

int main() {
    pow8[0] = 1;
    for (int i=1; i<=18; i++) pow8[i] = pow8[i-1] * 8;
    for (int i=0; i<=9; i++) for (int j=0; j<=9; j++) if (i!=j) dp[2][i][j] = 1;
    for (int u=3; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) {
                if (i!=j) {
                    for (int k=0; k<=9; k++) {
                        if (i!=k && j!=k) dp[u][i][j] += dp[u-1][j][k];
                    }
                }
            }
        }
    }
    for (int i=0; i<=9; i++) d[1][i] = 1;
    for (int u=2; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) d[u][i] += dp[u][i][j];
        }
    }
    sum[1][0] = 1;
    for (int u=1; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            if (!i && u!=1) sum[u][i] = sum[u-1][9];
            else sum[u][i] = sum[u][i-1] + d[u][i];
        }
    }

    if (debug) {
        for (int u=1; u<=18; u++) {
            cout << "u " << u << " : ";
            for (int i=0; i<=9; i++) cout << d[u][i] << ' ';
            cout << endl;
        }

        for (int u=1; u<=18; u++) {
            cout << "sum " << u << " : ";
            for (int i=0; i<=9; i++) cout << sum[u][i] << ' ';
            cout << endl;
        }
    }


    scanf(" %lld %lld", &a, &b);
    printf("%lld", sol(a, b));
}


/*long a, b, dp[20][15][15], d[20][15];

int main() {
    for (int i=0; i<=9; i++) for (int j=0; j<=9; j++) if (i!=j) dp[2][i][j] = 1;
    for (int u=3; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) {
                if (i!=j) {
                    for (int k=0; k<=9; k++) {
                        if (i!=k && j!=k) dp[u][i][j] += dp[u-1][j][k];
                    }
                }
            }
        }
    }

    if (debug) {
        for (int u=2; u<=18; u++) {
            for (int i=0; i<=9; i++) {
                cout << u << ' ' << i << " : ";
                for (int j=0; j<=9; j++) cout << dp[u][i][j] << ' ';
                cout << endl;
            }
        }
    }

    for (int i=0; i<=9; i++) d[1][i] = 1;
    for (int u=2; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) d[u][i] += dp[u][i][j];
        }
    }

    if (debug) {
        for (int u=2; u<=18; u++) {
            cout << "u " << u << " : ";
            for (int i=0; i<=9; i++) cout << d[u][i] << ' ';
            cout << endl;
        }
    }


    scanf(" %lld %lld", &a, &b);
    if (b == static_cast<long>(1e18)) b--;

    return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 11.25 / 25
• Subtask 2: 48.333333333333336 / 75