// 方法一:连乘积 + 和 作为Hash值,选择最接近N的质数P,当数据随机生成时,Hash值相同但雪花不同的冲突率极小,因此当冲突时 暴力判断即可,时间复杂度O(N * N/P);
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010, p = 99991;
int snow[N][6], h[N], ne[N], idx;
int hash(int* a) {
int sum = 0, mul = 1;
for (int i = 0; i < 6; i ++) {
sum += a[i];
mul = (LL) mul * a[i] % p;
}
return (sum + mul) % p;
}
bool equal(int* a, int* b) {
// 从任一位置出发,顺或逆时针遍历时对应角度完全相同,即为相同雪花;
for (int i = 0; i < 6; i ++)
for (int j = 0; j < 6; j ++) {
bool op = 1;
// 顺时针判定是否为同一雪花;
for (int k = 0; k < 6; k ++)
if (a[(i + k) % 6] != b[(j + k) % 6]) op = 0;
if (op) return true;
op = 1;
// 逆时针判定是否为同一雪花;
for (int k = 0; k < 6; k ++)
if (a[(i + k) % 6] != b[(j - k + 6) % 6]) op = 0;
if (op) return true;
}
return false;
}
bool insert(int* a) {
int val = hash(a);
// 哈希得到邻接表的位置,邻接表记录相同哈希值的雪花对应的snow数组下标;
for (int i = h[val]; i != -1; i = ne[i]) {
if (equal(snow[i], a)) return true;
}
memcpy(snow[idx], a, 6 * sizeof(int));
// 邻接表头插入;
ne[idx] = h[val];
h[val] = idx ++;
return false;
}
int main() {
int n; scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 0; i < n; i ++) {
int a[6];
for (int j = 0; j < 6; j ++) scanf("%d", &a[j]);
if (insert(a)) {
printf("Twin snowflakes found.\n");
return 0;
}
}
printf("No two snowflakes are alike.\n");
return 0;
}
// 方法二:以字符串的最小表示法作为判断雪花是否相同的依据,先求出每片雪花的最小表示法(顺时针与逆时针 -- 旋转 + 翻转),
// 然后按照最小表示法的字典序进行排序,相邻的两元素若字典序相同,则说明存在重复元素;时间复杂度O(NlogN)[主要源于排序];
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int snow[N][6];
int idx[N];
void tsf_min(int* s) {
int t[12];
for (int i = 0; i < 12; i ++) t[i] = s[i % 6];
int i = 0, j = 1, k;
while (i < 6 && j < 6) {
for (k = 0; k < 6 && t[i + k] == t[j + k]; k ++);
t[i + k] > t[j + k] ? i = i + k + 1 : j = j + k + 1;
if (i == j) j ++;
}
k = min(i, j);
for (i = 0; i < 6; i ++) s[i] = t[i + k];
}
// 若s1的字典序小于s2的字典序,则返回true;若a元素字典序 既小于 又大于 b元素字典序,则说明两元素字典序相同;
bool cmp_array(const int* s1, const int* s2) {
for (int k = 0; k < 6; k ++)
if (s1[k] < s2[k]) return true;
else if (s1[k] > s2[k]) return false;
return false;
}
bool cmp(const int& i, const int& j) { return cmp_array(snow[i], snow[j]); }
int main() {
int n; scanf("%d", &n);
int s1[6], s2[6]; // 分别代表顺时针与逆时针雪花的最小表示法;
for (int k = 0; k < n; k ++) {
for (int i = 0, j = 5; i < 6; i ++, j --) {
scanf("%d", &s1[i]);
s2[j] = s1[i];
}
tsf_min(s1); tsf_min(s2);
if (cmp_array(s1, s2)) memcpy(snow[k], s1, sizeof s1);
else memcpy(snow[k], s2, sizeof s2);
idx[k] = k;
}
sort(idx, idx + n, cmp);
bool flag = false;
for (int i = 1; i < n; i ++)
if (!cmp(idx[i - 1], idx[i]) && !cmp(idx[i], idx[i - 1])) {
printf("Twin snowflakes found.\n");
return 0;
}
printf("No two snowflakes are alike.\n");
return 0;
}