I'm afraid that i'm getting WA on 7-th test because of hash collisions. How to avoid it? Please, give me some recipes) I tried to change prime base - 31,43,57 - anyway WA#7.

Edited by author 07.11.2010 10:15

up

Try 3737 or 1717.

P=1000000007 - only this base helped me! 31,57 - and other small bases - sucks! BTW, I didn't take anything by modulo and I declared hash as integer not long long. Now I have only one question: why 5.000.000 pairs of integers eats ~40 MB memory(it's ok  - each pair - (4B+4B) *5.000.000 ~ 40) BUT!!! why 5000 000 pairs of <long long,int> eats ~80MB?? I expected
(  8B(long long)+4B(int)   )* 5.000.000 ~60MB!! very strange...

Edited by author 07.11.2010 20:58

Edited by author 07.11.2010 20:58

It's due to data alignment. sizeof(pair<long long, int>) == 16. 8B(long long) + 4B(int) + 4B(unused).