The probability of the algorithm generating a correct permutation is the same as the number of derangements of length n divided by the number of permutations of length n in the worst case (all zeros).

When n tends to infinity, this probability is 1/e (see Wikipedia page liked above for details). Which means that the expected number of tries is e. Now our n is at most 2*10^5 and not infinity, but even then, the probability is very close to 1/e.

From this we can conclude that the algorithm has an expected complexity O(e*n) or O(n) since e is a constant.

Also, using random_shuffle on codeforces to shuffle an array of size greater than 2^15 (32768) can lead to getting wrong answer or getting hacked, instead you should use shuffle() and your custom random function. Read more about it here.

What's up with all the code above the main function? I'm a beginner so that really confused me, is it necessary for the solution of this problem?