This wasn't exactly what I meant, but I agree that reserve() will work for F. The problem is that this workaround will only work for this particular problem because of the 10^9 restriction. Given less tight bound (10^18) it will still fail.

And with 12-hours open tests you can even generate counter test for any particular hash function from universal family (not necessarily identity) and any particular buckets_count. The only way to protect against this attacks seems to be random sampling of hash function from universal family with good source of entropy.

The point was — why do you even need to bother about such details on a contest if you can just use map instead? It might be a bit slower but at least it has worst-case guarantees and it allows you to focus on a problem itself.

Problem solving is fun. I don't think it's fun to protect against hashmap-attacks.

So, this was an "anti-hash" test against STL's unordered_map... I'm new to Educational Rounds so I didn't think people actually use dirty tricks like anti-hash and anti-quicksort. I don't get why people do this but this broke all solutions with unordered_map instead of map. Well, learned something new, won't be using unordered_map on contests next time :)

Could you please explain the test you used to hack so many F solutions? I tried to find something in common in the solutions you hacked but failed to see the pattern. Your test seems to be tricky.

In Linux all threads are created using exactly the same system call as processes. You just have to explicitly specify that you want the same address space. All the pthread* stuff is just some high-level wrappers around clone() (manpage) system call. So if you can create thread you pretty much can create process.

Well, it seems like volatile is indeed redundant in this case. Clobber "+m" should take care of all things. I put it there just in case. Because redundant information isn't a problem, but lack of information is. volatile also comes in handy in multithreaded programs, when you are messing up with custom synchronization/locking technique. Actually anything that involves shared memory involves volatile somehow. In regular programs volatile rarely used, because everything is already written (like synchronization primitives/threadsafe data structures...) and program uses high-level functions for this.

Just to make sure that value is actually changed. It gives information to the compiler that memory is changed indirectly (inside asm block), to avoid unexpected optimizations. Modern compilers have aggressive optimizations. If you used some value from memory, compiler probably saved it to intermediate register. Let's imagine, that you then called bitset on that memory and used value again. Compiler may decide: "Ok, he didn't even touched that mem variable, I'll use the old value". But it's wrong. You changed it inside asm block. Everything inside asm — direct instructions to processor, compiler doesn't know what you are doing there.

Following is also useful for GCC. Very fast ASM bit operations:

Note, that offset can be >=32, any valid offset will work. However, I didn't know if inline assembly allowed in CF. Should work.

/* Read bit and set to zero */
inline bool btr (volatile void * mem, size_t offset) {
	bool result;
	__asm__ (
		"btr %2, %1; setc %0;"
		: "=r" (result), "+m" (* (volatile long *) mem)
		: "r" (offset)
		: "cc");
	return result;
}

/* Read bit and set to one */
inline bool bts (volatile void * mem, size_t offset) {
	bool result;
	__asm__ (
		"bts %2, %1; setc %0;"
		: "=r" (result), "+m" (* (volatile long *) mem)
		: "r" (offset)
		: "cc");
	return result;
}

/* Bit value */
inline bool bittest (volatile void * mem, size_t offset) {
	bool result;
	__asm__ (
		"bt %1, %2; setc %0;"
		: "=r" (result)
		: "r" (offset), "m" (* (volatile long *) mem)
		: "cc");
	return result;
}

/* Set bit to one */
inline void bitset1 (volatile void * mem, size_t offset) {
	__asm__ ("bts %1, %0;" : "+m" (* (volatile long *) mem) : "r" (offset) : "cc");
}

/* Set bit to zero */
inline void bitset0 (volatile void * mem, size_t offset) {
	__asm__ ("btr %1, %0;" : "+m" (* (volatile long *) mem) : "r" (offset) : "cc");
}

I came up with a different solution for C that runs in O(N+logK^2) — http://mirror.codeforces.com/contest/327/submission/4018240 . It can be easily optimized to O(N+logK).