Submission #135510

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135510	2019-07-24T07:16:48 Z	임유진(#3251)	PIN (CEOI10_pin)	C++14	20 / 100	1000 ms	7420 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];
		}
		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

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	428 KB	Output isn't correct
2	Correct	45 ms	6904 KB	Output is correct
3	Incorrect	39 ms	6904 KB	Output isn't correct
4	Incorrect	10 ms	504 KB	Output isn't correct
5	Incorrect	11 ms	636 KB	Output isn't correct
6	Correct	609 ms	7208 KB	Output is correct
7	Correct	446 ms	7032 KB	Output is correct
8	Incorrect	12 ms	672 KB	Output isn't correct
9	Incorrect	17 ms	760 KB	Output isn't correct
10	Execution timed out	1073 ms	7416 KB	Time limit exceeded
11	Correct	619 ms	7224 KB	Output is correct
12	Execution timed out	1071 ms	7416 KB	Time limit exceeded
13	Incorrect	638 ms	7256 KB	Output isn't correct
14	Incorrect	600 ms	7160 KB	Output isn't correct
15	Execution timed out	1022 ms	7420 KB	Time limit exceeded
16	Incorrect	14 ms	632 KB	Output isn't correct
17	Execution timed out	1086 ms	7416 KB	Time limit exceeded
18	Incorrect	850 ms	7336 KB	Output isn't correct
19	Incorrect	970 ms	7392 KB	Output isn't correct
20	Execution timed out	1045 ms	7420 KB	Time limit exceeded