http://acm.pku.edu.cn/JudgeOnline/problem?id=3349Snowflake Snow Snowflakes原来用hash过的,后来发现mill竟然排序就过了,更惊奇的是用了一堆STL的东东。
mill一直是“自食其力”型选手,记得以前连STL里面的sort都懒得用,说自己写快排快些,习惯了。这次再看他代码,吓一跳,完全变了风格,里面动不动就是STL的东西,copy(),rotate(),reverse(),一堆,还有从没见过的lexicographical_compare(),算是长见识了,于是照着写了个,把代码留下,以后还用得着。
1
//3349
2
#include <algorithm>
3
using namespace std;
4
5
const int N = 100010;
6
7
int a[N][6];
8
int sign[N];
9
10
bool cmp(const int &x, const int &y)
{
11
return lexicographical_compare(a[x],a[x]+6,a[y],a[y]+6);
12
}
13
int main()
{
14
freopen("in.txt", "r", stdin);
15
int n, i, j;
16
int b[6];
17
scanf("%d", &n);
18
for(i=0; i<n; i++)
{
19
for(j=0; j<6; j++)
{
20
scanf("%d", b+j);
21
}
22
copy(b, b+6, a[i]);
23
for(j=0; j<5; j++)
{
24
rotate(b, b+1, b+6);
25
if(lexicographical_compare(b, b+6, a[i], a[i]+6))
26
copy(b, b+6, a[i]);
27
}
28
reverse(b, b+6);
29
for(j=0; j<6; j++)
{
30
rotate(b, b+1, b+6);
31
if(lexicographical_compare(b, b+6, a[i], a[i]+6))
32
copy(b, b+6, a[i]);
33
}
34
sign[i] = i;
35
}
36
sort(sign, sign+n, cmp);
37
for(i=1; i<n; i++)
{
38
if(memcmp(a[sign[i-1]], a[sign[i]], sizeof(a[0])) == 0)
{
39
printf("Twin snowflakes found.\n");
40
return 0;
41
}
42
}
43
printf("No two snowflakes are alike.\n");
44
return 0;
45
}
46
posted on 2007-08-18 13:03
LSM 阅读(611)
评论(0) 编辑 收藏 引用 所属分类:
STL