Submission #1167810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167810		tamyte	Cards (LMIO19_korteles)	C++17	19 / 100	141 ms	3972 KiB

korteles

#include <bits/stdc++.h>



using namespace std;
using ll = long long;
const int MAX = 26 * 26 * 26 * 26;
const int MAX1 = 26 * 26;
int cnt[MAX + 1];
char c[MAX + 1][4];
int L[MAX1 + 1], R[MAX1 + 1], U[MAX1 + 1], D[MAX1 + 1];

int hash2(char a, char b) {
	return 26 * (a - 'A') + (b - 'A');
}
int hash4(char  a[]) {
	int res = 0;
	for (int i = 0; i < 4; ++i) {
		res *= 26;
		res += (a[i] - 'A');
	}
	return res;
}
int hash4(int a, int b, int c, int d) {
	int res = 0;
	res += a;
	res *= 26;
	res += b;
	res *= 26;
	res += c;
	res *= 26;
	res += d;
	return res;
}

int main() {
	int n;
	cin >> n;
	ll res = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 4; ++j) {
			cin >> c[i][j];
		}
		L[hash2(c[i][0], c[i][2])]++;
		R[hash2(c[i][1], c[i][3])]++;
		U[hash2(c[i][0], c[i][1])]++;
		D[hash2(c[i][2], c[i][3])]++;
		cnt[hash4(c[i])]++;
		// II
		// JJ
		if (c[i][0] == c[i][1] && c[i][2] == c[i][3]) {
			res--;
		}
		// IJ
		// IJ
		if (c[i][0] == c[i][2] && c[i][1] == c[i][3]) {
			res--;
		}
	}
	for (int i = 0; i <= MAX1; ++i) {
		res += 1LL * L[i] * R[i];
		res += 1LL * U[i] * D[i];
	}
	// cout << res << endl;
	for (int i = 0; i < 26; ++i) {
		for (int j = 0; j < 26; ++j) {
			for (int k = 0; k < 26; ++k) {
				for (int l = 0; l < 26; ++l) {
					int h1, h2;
					// IJ   KL
					// KL   IJ
					// -1
					h1 = hash4(i, j, k, l);
					h2 = hash4(k, l, i, j);
					if (h1 < h2) {
						res -= 1LL * cnt[h1] * cnt[h2];
						// if (cnt[h1] + cnt[h2] == 2) {
							// cout << "-1\n";
						// }
					}
					// IJ  JI
					// KL  LK
					// -1
					h2 = hash4(j, i, l, k);
					if (h1 < h2) {
						res -= 1LL * cnt[h1] * cnt[h2];
						// if (cnt[h1] + cnt[h2] == 2) {
							// cout << "-1\n";
						// }
					}
					// IJ JL
					// KI IJ
					// -1
					// [(k = l), (l = k)]
					//     i  j  k  i    j  l  i  k
					// -2 (i, j, j, i); (j, i, i, j)
					h1 = hash4(i, j, k, i);
					h2 = hash4(j, l, i, j);
					if (h1 < h2) {
						// if (cnt[h1] && cnt[h2])
							// cout << h1 << " " << h2 << endl;
						res -= 1LL * cnt[h1] * cnt[h2];
						
					}
					// if (h1 != h2) {
						// // if (cnt[h1] && cnt[h2])
							// // cout << h1 << " " << h2 << endl;
						// res -= 1LL * cnt[h1] * cnt[h2];
					// }
					// KI IJ
					// IJ JL
					// -1
					//     k  i  i  j    i  j  j  l
					//  [(k = l), (l = k)]
					// -2 (i, j, j, i); (j, i, i, j)
					h1 = hash4(k, i, i, j);
					h2 = hash4(i, j, j, l);
					if (h1 > h2) {
						// if (cnt[h1] && cnt[h2])
							// cout << h1 << " " << h2 << endl;
						res -= 1LL * cnt[h1] * cnt[h2];
					}
					// if (h1 != h2) {
						// if (cnt[h1] && cnt[h2])
							// cout << h1 << " " << h2 << endl;
						// res -= 1LL * cnt[h1] * cnt[h2];
					// }
				}
			}
			// 4 - 6 + 3 = 1
			// IJ JI
			// JI IJ
			if (i < j) {
				res += 1LL * cnt[hash4(i, j, j, i)] * cnt[hash4(j, i, i, j)];
				// res += 3LL * cnt[hash4(i, j, j, i)] * cnt[hash4(j, i, i, j)];
			}
		}
	}
	cout << res << endl;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 19 / 19
• Subtask 5: 0 / 25