There is solution for all n <= 10^5 though I still can not fast enough generate answer

According to my calculations the largest such sequence can be 344001 for the constraints of the problem.

answer for every n exists
there is no possibility to output “impossible”

You have to use BigInteger, you can't simply use Long Long bc the answer can go up to 2^(1600)

Thanks

Centers of circles form a regular polygon with side length 2. Now, consider the formula to find circumradius of a regular polygon and add 1 because you were connecting circle centres, but not their tangent points to the circle.

i also have wa#6

Same here... got stuck in Test-16 .

It can be solved using O(log(n) + log(k)) rows.

Do it like that:

1) put AA right before # to the left. This is 00 written base 26.

2) go right until you encounter -. Put + there and then go left until you hit #. Increase that number (it will become AB). Then go right again.

3) if you encounter # while walking right, go left and compute coordinate of last - mathematically using cells to the left as memory with base-26 2-digit arithmetics. For arbitrary k and n it will be more than 2 of course, that's why it's O(log(k)+log(n)), but not a constant.

4) like in case of 2 run right/left by putting - instead of + until result becomes zero (decrease it with every - set).

5) Find rightmost - and paint everything to the left with +

6) Find - and stop there

Though, I heard in this forum that the checker is wrong as it stops when there are n-1 pluses, but not when invalid state/character pair is met. So, actually you will have to use O(n) states to calculate 'n' and then bring back this value to calculation area inside read/write head :)

My solution for each k output 604 lines.

I don't understand what you mean there.

In fact, the problem asks for an interval [l, r] to find the average cost of a sub-interval.

That is, as for the first test case. After two 'change' queries we have cost(1, 2) = 1; cost(2, 3) = 2, cost(3, 4) = 2. Then we are asked for the average on the interval [2, 4] which is (cost(2, 3) + cost(3, 4) + cost(2, 4)) / 3.



So, given an interval [l, r] you are asked to compute:

int64_t n_of_intervals = 0;
int64_t total_sum = 0;
for (int i = l; i < r; ++i)
   for (int j = i + 1; j <= r; ++j)
      n_of_intervals += 1
      total_sum += cost(i, j)
output total_sum / n_of_intervals

What do you mean under "the method of construction"? For example I solved it using greedy algo. And, as I know, it's very hard to prove that for some fixed n solution doesn't exist. Therefore jury checked a possibility of coloring artists for all n <= MAXN with a help of their own method (maybe, also greedy). According to this time limit and MAXN for this problem were selected.

Эта задача имеет математическое решение. Нам задан граф на N вершинах, причём степень каждой вершины p (нужно самому понять, откуда берётся p). Требуется покрасить вершины так, чтобы смежные имели разный цвет. Утверждение: покраска возможна <=> цветов >=p+1. Необходимость очевидна. А достаточность реализуется по индукции: пусть мы покрасили k<N вершин, так что смежные имеют разный цвет. Возьмём не покрашенную вершину. Её степень <=p, а цветов >=p+1.Тогда покрасим её в любой из оставшихся цветов.

I used fast I/O to get 0.031. There are faster input methods that use fwrite/fread while mine is based on getChar/writeChar. Perhaps using even faster I/O can get you to 0.015

[code deleted]

Edited by author 10.09.2019 14:33

Edited by moderator 24.11.2019 13:26

It's wrong. Because the last leaf of the max heap is not necessarily minimum but you are removing it (v.pop_back();). Your code may remove the median element.

And the sort_heap has no effect.

Решил с грехом пополам, здесь писать не буду. Остались сомнения, что в условии(в тестах) правильно размер массива подсчитан, этот(SIZE) не катит.

Use Segment Trees with lazy propagation