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;
}