Submission #135674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135674	2019-07-24T09:38:59 Z	onjo0127	PIN (CEOI10_pin)	C++11	100 / 100	479 ms	12092 KB

pin

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

int N, D;
unordered_map<string, int> mp;
string S[50009];

string make(string S, int msk) {
	for(int i=0; i<4; i++) if((msk >> i) & 1) S[i] = '_';
	return S;
}

long long solve1() {
	long long ans = 0;
	for(int i=1; i<=N; i++) {
		ans += mp[make(S[i], 1)];
		ans += mp[make(S[i], 2)];
		ans += mp[make(S[i], 4)];
		ans += mp[make(S[i], 8)];
	}
	return ans;
}

long long solve2() {
	long long ans = 0;
	for(int i=1; i<=N; i++) {
		ans += mp[make(S[i], 3)];
		ans += mp[make(S[i], 5)];
		ans += mp[make(S[i], 9)];
		ans += mp[make(S[i], 6)];
		ans += mp[make(S[i], 10)];
		ans += mp[make(S[i], 12)];

		ans -= 3*mp[make(S[i], 1)];
		ans -= 3*mp[make(S[i], 2)];
		ans -= 3*mp[make(S[i], 4)];
		ans -= 3*mp[make(S[i], 8)];
	}
	return ans;
}

long long solve3() {
	long long ans = 0;
	for(int i=1; i<=N; i++) {
		ans += mp[make(S[i], 14)];
		ans += mp[make(S[i], 13)];
		ans += mp[make(S[i], 11)];
		ans += mp[make(S[i], 7)];

		ans -= 2*mp[make(S[i], 3)];
		ans -= 2*mp[make(S[i], 5)];
		ans -= 2*mp[make(S[i], 9)];
		ans -= 2*mp[make(S[i], 6)];
		ans -= 2*mp[make(S[i], 10)];
		ans -= 2*mp[make(S[i], 12)];

		ans += 3*mp[make(S[i], 1)];
		ans += 3*mp[make(S[i], 2)];
		ans += 3*mp[make(S[i], 4)];
		ans += 3*mp[make(S[i], 8)];
	}
	return ans;
}

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> D;
	for(int i=1; i<=N; i++) {
		cin >> S[i];
		for(int j=1; j<16; j++) ++mp[make(S[i], j)];
	}
	for(auto& it: mp) --it.second;
	long long ans = 0;
	if(D == 1) cout << solve1() / 2;
	if(D == 2) cout << solve2() / 2;
	if(D == 3) cout << solve3() / 2;
	if(D == 4) cout << (1LL*N*(N-1) - solve1() - solve2() - solve3()) / 2;
	return 0;
}

Compilation message

pin.cpp: In function 'int main()':
pin.cpp:75:12: warning: unused variable 'ans' [-Wunused-variable]
  long long ans = 0;
            ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	2424 KB	Output is correct
2	Correct	9 ms	2552 KB	Output is correct
3	Correct	10 ms	2368 KB	Output is correct
4	Correct	58 ms	3320 KB	Output is correct
5	Correct	67 ms	3320 KB	Output is correct
6	Correct	85 ms	3320 KB	Output is correct
7	Correct	69 ms	3320 KB	Output is correct
8	Correct	82 ms	3448 KB	Output is correct
9	Correct	120 ms	3420 KB	Output is correct
10	Correct	166 ms	3576 KB	Output is correct
11	Correct	104 ms	3408 KB	Output is correct
12	Correct	194 ms	3448 KB	Output is correct
13	Correct	122 ms	3372 KB	Output is correct
14	Correct	156 ms	3320 KB	Output is correct
15	Correct	254 ms	3448 KB	Output is correct
16	Correct	147 ms	9476 KB	Output is correct
17	Correct	290 ms	12088 KB	Output is correct
18	Correct	431 ms	11524 KB	Output is correct
19	Correct	479 ms	11620 KB	Output is correct
20	Correct	462 ms	12092 KB	Output is correct