Da ya shutkuyu prost))

required from ‘class std::vector<int, int>’ CandidatesSelectionEasy.cc:14:21: 
...
 error: ‘int’ is not a class, struct, or union type 

Казалось бы, действительно, int — так себе аллокатор.

Me too so my score in 250 is low just discovered that function name is sort :D
so I make another function outside it called SRT then i add sort function inside it :D
actually I don't know why the writer use sort as a function name :( :(

Здесь была написана фигня =)

Я локально запустил программу с двумя миллионами создаваемых элементов в map <pair <int, int>, int>, увидел 0.7 секунды и успокоился.

Можно просто жадно добавлять с конца то, что не противоречит конфигурации. Если добавили всё что получилось, а сортировка всё ещё неправильная, значит Impossible.

Решение. Во-первых, применять один и тот же порядок два раза бесполезно.

Будем строить ответ с конца. Изначально все элементы образуют один класс.

Найдем какой-нибудь неиспользованный порядок, который согласован, и применим его последним. Порядок можно применять, если для всех соседних в одном классе, он такой как надо. Если можно применять, применим.

При этом какие-то классы распались на части.

В конце, все классы должны быть упорядоченны (то есть в том порядке, в котором было изначально).

Строго не доказывал, если махать руками, все действия остаются возможными, поэтому если применим будет не хуже.

У меня была идея, но она упала. Как будет дорешка — смогу точно сказать, идея лажа или реализация.

В общем, для пары параметров определяем, могли ли они следовать друг за другом в цифровой сортировке. Утверждается, что если могли, то если мы возьмём элементы с одинаковым первым параметром, они будут отсортированы по второму параметру. Также добавляем параметр, равный для каждого кандидата его начальному положению. И помечаем параметры, которые могут быть замыкающими, то есть, в итоге у нас посортировано по ним. Моё предположение: ответ есть, если есть путь по параметрам от добавленного фиктивного к любому "хорошему".

Гауссом по модулю два. Каждое число — переменная. Считаем число независимых переменных, ответ — 2^ans. Условия — на строки, на столбцы, а дальше каждое число развалили на простые и получили еще X строк, где X — количество различных простых.

Совершенно стандартная задача на линейные уравнения по модулю.

Посмотроим такую систему уравнений по модулю 2, что каждое решение — это одной из решений нашей задачи. В этой системе будет n² переменных, каждая переменная a[i][j] отвечает за то, берем мы в ответ соотвествующее число или нет. Уравнения, которые нужно записать:

В последнем уравнении p — это простое число (одно из тех, которые содержатся в заданных числах). power(p, x) — в какой степени число p встречается в x.

Дальше нужно алгоритмом Гаусса найти ранг матрицы r, ответ на задачу 2^n2 - r.

It's classic exercise for Gauss elimination.

You have n² variables, 2n rows to fix parity of number of selected numbers in each row/column and then we have one additional row for each prime number which occurs in the input.

After you solve the system, you will either get contradiction or number of free variables. Answer is 2 to this number.

I have an idea, but I don't know if it's correct. I'll try to code it, and will post UPD with results

Let's find the answer for n = 4 first. Now we can use inclusion-exclusion principle to calculate probability for at least one event (connected component with >= 4 verteces) happen.

It is more convenient to answer the complementary question of what is the probability that all connected components are of size at most 3. This can be done with a one-dimensional dynamic programming with the state being the number of vertices. To build the transitions observe that there are only three possible choices for Vertex 1: it may be in a component by itself, it may be connected to exactly one other vertex and form a component with it or it can be in a component of size 3.

We can use greedy algorithm, If some skill not contradict, we take this skill to sort. Take skills while it is possible. :)