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>
3using namespace std;
4
5const int N = 100010;
6
7int a[N][6];
8int 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
}
13int 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 閱讀(619)
評論(0) 編輯 收藏 引用 所屬分類:
STL