Submission #135515

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135515	2019-07-24T07:20:34 Z	임유진(#3251)	PIN (CEOI10_pin)	C++14	70 / 100	1000 ms	7424 KB

pin

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

typedef long long lint;

const int MAXN = 50005;
const int TOTAL = 36 * 36 * 36 * 36;

char p[MAXN][5];
int cnt[TOTAL];
const int pw[4] = {36 * 36 * 36, 36 * 36, 36, 1};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, D;
	lint ans = 0ll;

	cin >> N >> D;
	for(int i = 0; i < N; i++) cin >> p[i];

	for(int i = 0; i < N; i++) for(int j = 0; j < 4; j++)
		p[i][j] = '0' <= p[i][j] && p[i][j] <= '9' ? (p[i][j] - '0') : (p[i][j] - 'a' + 10);

	lint one = 0, two = 0, thr = 0, fou = 0;
	if(D != 1) {
		for(int i = 0; i < N; i++) {
			//printf("two = %lld\n", two);
			char tmp[4];
			int x = 0;
			for(int j = 0; j < 4; j++) {
				tmp[j] = p[i][j];
				x += p[i][j] * pw[j];
			}
			two += cnt[x];
			for(int j = 0; j < 4; j++) {
				for(tmp[j] = 0, x -= p[i][j] * pw[j]; tmp[j] < 36; tmp[j]++, x += pw[j]) if(tmp[j] != p[i][j]) {
					for(int k = j + 1; k < 4; k++) {
						for(tmp[k] = 0, x -= p[i][k] * pw[k]; tmp[k] < 36; tmp[k]++, x += pw[k]) if(tmp[k] != p[i][k]) 
							fou += cnt[x]++;
						tmp[k] = p[i][k];
						x += (p[i][k] - 36) * pw[k];
					}
					thr += cnt[x];
				}
				tmp[j] = p[i][j];
				x += (p[i][j] - 36) * pw[j];
			}
		}
		for(int i = 0; i < TOTAL; i++) cnt[i] = 0;
	}
	for(int i = 0; i < N; i++) {
		char tmp[4];
		int x = 0;
		for(int j = 0; j < 4; j++) {
			tmp[j] = p[i][j];
			x += p[i][j] * pw[j];
		}
		cnt[x]++;
		for(int j = 0; j < 4; j++) {
			for(tmp[j] = 0, x -= p[i][j] * pw[j]; tmp[j] < 36; tmp[j]++, x += pw[j]) if(tmp[j] != p[i][j]) 
				one += cnt[x];
			tmp[j] = p[i][j];
			x += (p[i][j] - 36) * pw[j];
		}
	}

	thr = (thr - 105 * one - 68 * two) / 3;
	fou = (fou - 3570 * one - 1296 * two - 204 * thr) / 6;
	//printf("zero = %lld, one = %lld, two = %lld, thr = %lld, fou = %lld\n", zero, one, two, thr, fou);

	if(D == 1) ans = one;
	else if(D == 2) ans = two;
	else if(D == 3) ans = thr;
	else ans = fou;

	cout << ans;
	return 0;
}

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1656 KB	Output is correct
2	Correct	47 ms	6948 KB	Output is correct
3	Correct	38 ms	6908 KB	Output is correct
4	Correct	12 ms	1912 KB	Output is correct
5	Correct	13 ms	1912 KB	Output is correct
6	Correct	538 ms	7212 KB	Output is correct
7	Correct	438 ms	7164 KB	Output is correct
8	Correct	16 ms	1916 KB	Output is correct
9	Correct	23 ms	2168 KB	Output is correct
10	Execution timed out	1075 ms	7416 KB	Time limit exceeded
11	Correct	588 ms	7220 KB	Output is correct
12	Execution timed out	1058 ms	7424 KB	Time limit exceeded
13	Correct	670 ms	7164 KB	Output is correct
14	Correct	624 ms	7288 KB	Output is correct
15	Execution timed out	1031 ms	7416 KB	Time limit exceeded
16	Correct	26 ms	7288 KB	Output is correct
17	Execution timed out	1067 ms	7416 KB	Time limit exceeded
18	Correct	842 ms	7388 KB	Output is correct
19	Execution timed out	1002 ms	7416 KB	Time limit exceeded
20	Execution timed out	1075 ms	7416 KB	Time limit exceeded