I dont know about your time zone but it is saturday here :D

Organising in two or three different days of week and two different times will help everybody to participate.

Я надеюсь, что завтра с утра будет финальная его версия.

int n, m, d=1; 
cin >> n >> m;
int i;

for (i = 0; i < 2*m; i += 2)
{
    cout << d << ' ' << d+1 << ' ';
    d += 2;
}

for (i; i < 2*n; i += 2)
{
    cout << d + 1 << ' ' << d << ' ';
    d += 2;
}

Ставишь числа в виде 2 1 4 3 6 5 ... И потом K раз меняешь местами числа в соседних парах, например, для k=2 ответом будет: 1 2 3 4 6 5 ...

Возьмем перестановку n, n-1, ..., 1. Для неё значение рассматриваемой разности равно нулю. Если менять местами элементы с номерами 2i и 2i — 1, разность будет увеличиваться на 2 с каждой заменой. Таким образом можно сделать k замен, и разность станет равной 2k.

А можно по-другому:

На первое место поставить число 1, на второе K+1, остальные числа отсортировать по убыванию. Если аккуратно раскрыть скобочки, видно что отсортированная часть сократится.

Мой код: http://codeforces.net/contest/359/submission/4963564

Upd. Отдельно рассмотреть случай K = 0. Тогда просто отсортируем по убыванию.

Можно было сразу сливать перестановку в вывод:

for (int i = 2*k+1; i > 0; i--) {
    cout<<i<<" ";
}
for (int i = 2*k+2; i <= 2*n; i++) {
    cout<<i<<" ";
}

Если на бумажке проверить аккуратно, то такая последовательность всегда проходит

same with you...test case 18

Nevermind :)

i found my mistake....if anybody would like, compare WA (4967509) and AC (4968673) yourself!

HINT: there is just one extra character in the AC code than the WA one. :P

8 2 5 5 5 5 4 4 2 0 this test case fails your solution.

Заметим, что каждое число может принадлежать только одному искомому интервалу [l..r]. Далее будем рассматривать каждое из чисел, начиная с наименьших, и искать максимальный интервал, содержащий данное число. Если число уже было отнесену к какому-нибудь интервалу, то его больше рассматривать не нужно, поэтому имеет решение за O(N).

systest is O(0.000001), but the rating update is O(n!!!!!!!) :(

They are my friends (bad friends :D ) and one of them knows my account password !

you can see submited codes for problems A B C are diffrent !

My subs : 4961619 4962635 4967645

Their subs :4962419 4963602 4966596

I changed my account password ...

And this ones. http://codeforces.net/contest/359/submission/4967310 http://codeforces.net/contest/359/submission/4965227

First time to see a new user care about cheaters !!!!???!!

Chill, one of them is in virtual participation.

My solution is the same as that. But my coding is ugly...

BTW, what book is it? It seems quite helpful.

Let me explain my way of looking at it. I will take an example. n = 2, k = 1. Firstly, my permutation should have 2*n = 4 elements. For now, I do not know anything about it so let's say it is:

a1, a2, a3, a4.

According to the given formula,

(|a1-a2| + |a3-a4|)-(|a1-a2 + a3-a4|) = 2*k

In LHS of the above equation, Let's denote expression inside first parantheses as A1 and second as A2.

Now, 2*k is always even. It means that there are 'k' terms which are being added to A1, and 'k' terms which are being subtracted in A2. One way of looking at it can be:

A1 = C+k

A2 = C-k

where C is some constant.

How can I form an expression such that k gets added in A1 and gets subtracted in A2? By reversing exactly k pairs whose absolute difference is 1!

So, if my sequence was 4 3 2 1.

A1 = (|4-3| + |2-1|) = 2.

A2 = (|4-3 + 2-1|) = 2.

Say I reverse exactly 1 pair, (2, 1) becomes (1, 2).

New sequence = 4 3 1 2.

A1 = (|4-3| + |1-2|) = 2.

A2 = (|4-3 + 1-2|) = 0.

A1-A2 = 2 = 2*(1) = 2*k!

One more example, n = 4, k = 2. I will just give the answer. It is based on the explanation above.

Answer : 8 7 6 5 3 4 1 2.

Notice that two pairs (2, 1) and (4, 3) have been flipped.

General solution: Just form a permutation sorted in descending order and flip 'k' pairs as illustrated above.

6 is not a prime :) so invalid

even i wasted a lot of time thinking that a factor of x could reduce the denominator and hence would have to be accounted for. then i reread the problem and saw that x must be prime. started coding the solution immediately after that! :)

Depending on how well written it is, it would be possible for it to pass, but my O(40N) takes 0.35s, so it might just TLE.

EDIT: Mine is . I forgot about GCD working in . So yeah, it should pass.

i think my solution is O(N * lg n ^ 2) in best form and O(N * lg N ^ 3) in worst form. (but im not sure!) it get accepted in 1300ms. i Think Your Solution will be accept too! here is my solution : 4967080

That's just what I was talking about above, that a well-written solution would pass. In this case, there's an additional factor of to the complexity, so a segment tree, which has a large constant compared to some other approaches (sparse table for example), can get TLE.

Seeing as it takes 1.5s on case 9 with N = 2·10⁵, it probably just needs some small optimization to pass.