oj.uz

답안 #518225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518225 2022-01-23T08:58:54 Z Ai7081 Palindrome-Free Numbers (BOI13_numbers) C++17
59.5833 / 100
 1 ms 364 KB 
#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;
}*/

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #2
48.3333333333 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 1 ms 308 KB Output isn't correct
7 Correct 1 ms 332 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 312 KB Output isn't correct
12 Correct 1 ms 332 KB Output is correct
13 Incorrect 1 ms 332 KB Output isn't correct
14 Incorrect 1 ms 204 KB Output isn't correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Incorrect 1 ms 332 KB Output isn't correct
32 Correct 1 ms 204 KB Output is correct
33 Incorrect 1 ms 332 KB Output isn't correct
34 Correct 1 ms 332 KB Output is correct
35 Incorrect 1 ms 332 KB Output isn't correct
36 Incorrect 1 ms 336 KB Output isn't correct
37 Incorrect 1 ms 332 KB Output isn't correct
38 Incorrect 1 ms 332 KB Output isn't correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Incorrect 0 ms 332 KB Output isn't correct
42 Correct 1 ms 332 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Incorrect 1 ms 332 KB Output isn't correct
45 Incorrect 1 ms 332 KB Output isn't correct