POJ 3349 Snowflake Snow Snowflakes
問題
雪の結晶は6つの整数により表される。
ただし、整数の順序をシフトさせたものや、順序を反転させたものは同一である。
与えられる雪の結晶の中に、同一の二つがあるなら
Twin snowflakes found.を、そうでないなら
No two snowflakes are alike.を出力せよ。
制約条件
結晶の数≦100000
方針
ハッシュ化してハッシュテーブルに入れる。
結晶は、回転や反転が出来るので、回転反転を全通り試し、辞書順最小のものをもっておく。
setにそのままつっこむとTLE.
setにハッシュ化してつっこんでもTLE.
ハッシュテーブルに入れると制限時間内で通るようになった。
ソースコード
const int MX=999997; ll tab[MX]; inline void put(ll hash){ int i=hash%MX; for(;tab[i];i=i<MX-1?i+1:0); tab[i]=hash; } inline bool contain(ll hash){ int i=hash%MX; for(;tab[i];i=i<MX-1?i+1:0){ if(tab[i]==hash)return 1; } return 0; } inline bool cmp(int *a,int *b){ rep(i,6)if(a[i]!=b[i])return a[i]>b[i]; return 0; } int main(){ int n,m; scanf("%d",&n); rep(i,n){ int arm[6], regular[6]; rep(j,6)scanf("%d",arm+j), regular[j]=arm[j]; rep(j,12){ if(cmp(regular,arm))rep(k,6)regular[k]=arm[k]; rotate(arm,arm+1,arm+6); if(j==5)reverse(arm,arm+6); } ll hash=0; rep(j,6)hash*=10003, hash+=regular[j]+37; if(contain(hash)){ puts("Twin snowflakes found."); return 0; } put(hash); } puts("No two snowflakes are alike."); return 0; }