Computing the de Bruijn sequence
The 'prefer-1' algorithm works by having a current word, shifting out the first bit and then appending a new bit. 

Such a current word - which essentially represents the tail of the sequence constructed thus far - could be housed in a machine word (word-sized variable or register) for lengths up to 32 or 64 bits. The new bit that you decide on during each iteration can then be converted to text and appended to the answer, which would obviously have been initialised to the textual representation of the all-0 word before the loop.

Your implementation does not keep such a current word. Instead you reconstruct the current word at each step from the textual representation of the sequence, by looking at its tail.

If you remove this inefficiency then your code ought to be fast enough to beat the generous timeout.

Also, your code can benefit from a bit of refactoring - moving the code for constructing the sequence out of main() into its own function - and from a thorough spring cleaning.

E.g. the expression (1&lt;&lt;n) does not change during the computation but you recompute for every iteration of the outer loop. usedN looks ugly and is not very informative; what about words_found? Or change things around to

for (unsigned words_to_find = 1u &lt;&lt; n - n; words_to_find--; )
{
   ...
}


This must work since you find exactly one new word during each iteration. The term is (1 &lt;&lt; n) - n because n characters have already been appended to the output sequence; other loop structures are possible but then the loop logic would have to be adapted.

Try to change your code so that it reads more like a description of what you're doing. Including asserts can help clarify things both for you and the reader, and it can help finding mistakes early.

For example, the 'prefer 1' algorithm implies that if the new word with a 1 already exists, then swapping the 1 for a 0 must result in word that does not exist yet. Assuming the current new word to be housed in a variable current_word:

if (used[current_word])
   current_word &amp;= ~1u;  // change the new bit to zero

assert(not used[current_word]);
used[current_word] = true;

ans.push_back('0' + (current_word &amp; 1u));


Or, if you enjoy terse code:

current_word ^= used[current_word];
...


But then you need to be careful about only writing strict 1 (i.e. true) into the array. Other non-zero values would also evaluate to true in conditions but they would completely mess up the terse code.

For an example that uses an integer working variable I'm appending a simple, straightforward Delphi rendition of the code (since I need to learn Delphi ATM). It clocks about 50 ms for n = 20, and a C++ version should be even faster. The code can be made significantly faster still for higher n, by using a packed bitmap and preallocating the result string (i.e. calling reserve() in C++).

function DeBruijn_sequence (n: Cardinal): string;
var
   seen: array of Boolean;
   bits: Cardinal;
   mask: Cardinal;
   i: Cardinal;
   w: Cardinal;
begin
   bits := 1 shl n;
   mask := bits - 1;
   assert(bits &lt;&gt; 0);
   SetLength(seen, bits);
   result := StringOfChar('0', n);
   w := 0;
   for i := n + 1 to bits do begin
      seen[w] := true;
      w := ((w shl 1) or 1) and mask;
      if seen[w] then begin
         w := w and not 1;
         assert(not seen[w]);
      end;
      result := result + Char(Byte('0') + (w and 1));
   end;
end;