Submission #135402

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135402	2019-07-24T04:53:04 Z	imeimi2000	PIN (CEOI10_pin)	C++17	100 / 100	33 ms	8056 KB

pin

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long llong;

int n, d;
int cnt[16][36 * 36 * 36 * 36];
int tr[256];
char S[50001][5];

llong nCr[9][9];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    nCr[0][0] = 1;
    for (int i = 1; i < 9; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j > 0) nCr[i][j] += nCr[i - 1][j - 1];
            if (j < i) nCr[i][j] += nCr[i - 1][j];
        }
    }
    for (int i = 0; i < 10; ++i) tr[i + '0'] = i;
    for (int i = 0; i < 26; ++i) tr[i + 'a'] = i + 10;
    cin >> n >> d;
    d = 4 - d;
    for (int i = 0; i < n; ++i) {
        cin >> S[i];
        for (int j = 0; j < 16; ++j) {
            int val = 0;
            for (int k = 0; k < 4; ++k) {
                if ((j >> k) & 1) {
                    val *= 36;
                    val += tr[S[i][k]];
                }
            }
            ++cnt[j][val];
        }
    }
    llong ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 16; ++j) {
            int val = 0, bit = 0;
            for (int k = 0; k < 4; ++k) {
                if ((j >> k) & 1) {
                    val *= 36;
                    val += tr[S[i][k]];
                    ++bit;
                }
            }
            if (d <= bit) {
                if ((bit - d) & 1) ans -= nCr[bit][bit - d] * cnt[j][val];
                else ans += nCr[bit][bit - d] * cnt[j][val];
            }
        }
    }
    printf("%lld\n", ans / 2);
    return 0;
}

Compilation message

pin.cpp: In function 'int main()':
pin.cpp:35:38: warning: array subscript has type 'char' [-Wchar-subscripts]
                     val += tr[S[i][k]];
                                      ^
pin.cpp:48:38: warning: array subscript has type 'char' [-Wchar-subscripts]
                     val += tr[S[i][k]];
                                      ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2296 KB	Output is correct
2	Correct	4 ms	2168 KB	Output is correct
3	Correct	4 ms	2040 KB	Output is correct
4	Correct	10 ms	2296 KB	Output is correct
5	Correct	12 ms	2296 KB	Output is correct
6	Correct	12 ms	2296 KB	Output is correct
7	Correct	10 ms	2172 KB	Output is correct
8	Correct	13 ms	2296 KB	Output is correct
9	Correct	18 ms	2296 KB	Output is correct
10	Correct	20 ms	2396 KB	Output is correct
11	Correct	12 ms	2168 KB	Output is correct
12	Correct	19 ms	2296 KB	Output is correct
13	Correct	13 ms	2296 KB	Output is correct
14	Correct	13 ms	2296 KB	Output is correct
15	Correct	21 ms	2268 KB	Output is correct
16	Correct	22 ms	7928 KB	Output is correct
17	Correct	31 ms	8056 KB	Output is correct
18	Correct	25 ms	8056 KB	Output is correct
19	Correct	28 ms	8056 KB	Output is correct
20	Correct	33 ms	8056 KB	Output is correct