PKU 3640 Conformity

問題

n人の人の時間割が与えられる。
時間割は5つの授業の番号により与えられる。

同じ時間割（順序を入れ替えても同じとみなす）の人数が最大である時間割
（複数ある場合は全て）を選んだ人数を求めよ。

制約条件

n≦10000
時間割番号は100以上499以下

方針

時間割はlong longの整数一つで表せるので、
これをmapに入れて数える。

STLのmapを使うとTLEなので、
適当にhashmapなどを使う。

ソースコード

template<class K, class V>struct Map{
	ll *hs;
	V *data;
	const static int SZ = 29989;
	Map(){
		hs = new ll[SZ]; data = new V[SZ];
		rep(i, SZ) hs[i] = ~0;
	}
	~Map(){ delete(hs); delete(data); }
	
	ll hash(const K &key) const{
		return key;
	}
	int set(const K &key, const V &value){
		ll h = hash(key); int i = h % SZ;
		for(; hs[i] != h && hs[i] != ~0; i = i == SZ - 1 ? 0 : i + 1);
		hs[i] = h;
		data[i] = value;
		return i;
	}
	V get(const K &key) const{
		ll h = hash(key), i = h % SZ;
		for(; hs[i] != h && hs[i] != ~0; i = i == SZ - 1 ? 0 : i + 1);
		if(hs[i] != h) return 0; //no such key
		return data[i];
	}
};

int n, ixs[10000];

int main(){
	Map<ll, int> m;
	
	while(scanf("%d", &n), n){
	
		int mx = 0, ans = 0;
		rep(i, n){
			int a[5];
			rep(j, 5) scanf("%d", a + j);
			sort(a, a + 5);
			ll h = 0;
			rep(j, 5) h *= 400, h += a[j] - 100;
			
			int k = m.get(h) + 1;
			ixs[i] = m.set(h, k);
			if(mx < k) mx = k, ans = 0;
			if(mx == k) ans++;
		}
		printf("%d\n", mx * ans);
		
		rep(i, n) m.hs[ixs[i]] = ~0;
	}
	return 0;
}