Restrictions for a and b allow to use integer coefficients when line formed by any two points from square where triangle can be located.

Upper bound for a² + b² is redundant and should be set to maximum a² + b² value. Unfortunately it was set twice smaller and this mistake was found too late. Nevertheless it's easy to divide a, b and c by 2 and satisfy to restrictions without double precision loss.

У нас зашло после отсечения "если до клетки в принципе не дойти, то нам пофиг есть там стена или нет". Так склеивается сильно больше состояний.

На самом деле ключевыми были две оптимизации. Первая — кешировать состояния, ведь на старте может быть много повторов для большинства тестов, второе — исключать из битовой маски уничтоженных стен те, которые уже не могут быть достигнуты из текущего состояния ни при каком возможном сценарии. В одном из авторских решений по таким состояниям делается обычный BFS. Переходы между состояниями рекомендуется делать за O(1), особенно это касается выстрелов. Для каждого положения танка и состояния (целых и разрушенных) клеток в той же строке и том же столбце можно заранее определить все возможные переходы. После чего доставать их, например, из хеш-таблицы за O(1). Можно воспользоваться и другими способами.

Идея правильная, я таким же способом сдал. Тоже было WA 9, там нужно было long long использовать.

Мы перебирали x, через нашего в сток идет x, через остальных, кроме 'не прийти', идет x-1 в некую вершину Z, из 'не прийти' в Z идет инф, из Z в сток идет N-x. И ничего переманивать не нужно

можно вместо жадности в конце, поставить x пропускной способности и -INF стоимости

For each suffix compute the value (as a decimal number) mod P. Let a_i be the value corresponding to the suffix starting at i.

Then, for a fixed j, the value of the substring [i..j) only depends on a_i. Now it's easy to get an O(nlogn) solution for each query.

unordered_map + reserve заходит за 0.7.

Наш исходник: https://gist.github.com/yarrr-ru/61da2acffff64b1a35117938fff83564

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

I think 5th is MCMF problem. You can fix number of people who votes for no one, and maximum votes that other candidates get. Then build network with this variables and run MCMF. But not sure about whether it fits in time limit or not. I didn't have time to code it at contest because of 11th problem time limit in DIV2 :) I hope someone who solved it will write more detailed solution.

I solved it with MCMF.

Let a be the exact number of votes that we want our winning candidate to receive. Construct a flow graph with source/sink, a node for each person that is voting (N nodes), and a node for each voting option (K + 1 nodes). We need the following edges:

• Source to the node corresponding to our candidate with capacity a and a very large negative cost.
• Source to the other candidate that can be voted for with capacity a - 1 and zero cost.
• Source to "not voting" with infinite capacity and zero cost.
• Each voter to sink with capacity 1 and zero cost.
• Each voter to the voting option with capacity 1 and cost equal to the cost of having that voter choice that voting option.

It is clear that the minimum-cost flow here corresponds to the minimum cost required to have our candidate win with exactly a votes (the large negative cost from the source to our candidate forces any minimum-cost max flow to vote for our candidate a times). We can increment the cost of this flow by a·(negativecost) to get the exact cost, and look at the residual graph to reconstruct the solution. Finally, we can iterate a from 1 to N to get the optimal assignment.

Закрытие олимпиады завтра, вряд ли монитор онсайта разморозят до него.

1) Brute first K moves.

2) After that you have state (X, Y, DestructedWalls). For optimizations purpose DestructedWalls can be 64 bit mask.

3) Clean up bits in DestructedWalls mask, if you can't visit some walls anymore with (n - K) moves (to reduce different masks count).

4) After that there are not so many different states. For each just brute remain (n - K) moves.

K ~= 23 - 24 works for us in upsolving.

For F: take any remainder x modulo M. Now consider the chain of segments: [x, x], [b*x, b*(x+1)-1], [b*b*x, b*b*(x+1)-1], ... Find the first segment in this chain that contains 0 modulo M. The pair (k, (x*b**k) mod M) now uniquely defines state x, where k is the number of the segment (in other words, the size of the segment and its left boundary).

C: we will only use "is intersection empty" questions. First, find bounding box using binary searches by X and Y. At least one of its corners is a vertex of the triangle, we can check by truncating a small 0.5*0.5 triangle from the corner. Now we've found a vertex and a 90 degree angle containing everything. Now use two binary searches by angle to find rays containing two sides from that vertex. Finally, use binary searches with half-planes parallel to one side to find the vertex on the other side.

D: I find it really hard to explain, but the solution itself is really easy. First, the problem easily boils down to: you have N left ends, then N right ends of segments, connected somehow in pairs. Let's call two segments connected if they intersect, but not one lies inside another. Now we need to find connected components, check if each component is bipartite, and color with two colors if it is, all faster than N**2.

It turns out that because all left ends come before all right ends, the structure is really simple. Let's look at the left end corresponding to the first right end. All left ends after it intersect it, and thus must have the opposite color. Thus, their right ends must go in reverse order (to avoid intersections between them). Now let's consider the rightmost right end of those. All remaining uncolored right ends to the left of it, again, must have the first color, and so on.

Code for the coloring part:

        vector<double> sum_inside(2);
        vector<double> sum_outside(2);
        int bl = 0;
        int el = 0;
        int br = 0;
        int er = 1;
        double res = 0;
        while (true) {
            bool upd = false;
            int prev = -1;
            for (int ir = br; ir < er; ++ir) {
                int cur = invr[ir];
                if (color[cur] < 0) {
                    upd = true;
                    color[cur] = 0;
                    sum_inside[0] += inside[cur];
                    sum_outside[0] += outside[cur];
                    if (l[cur] < prev) {
                        out << -1 << endl;
                        return;
                    }
                    prev = l[cur];
                }
            }
            br = er;
            el = max(el, prev + 1);
            prev = -1;
            for (int il = bl; il < el; ++il) {
                int cur = invl[il];
                if (color[cur] < 0) {
                    upd = true;
                    color[cur] = 1;
                    sum_inside[1] += inside[cur];
                    sum_outside[1] += outside[cur];
                    if (r[cur] < prev) {
                        out << -1 << endl;
                        return;
                    }
                    prev = r[cur];
                }
            }
            bl = el;
            er = max(er, prev + 1);
            if (!upd) {
                assert(bl == el);
                assert(br == er);
                assert(el == er);
                res += min(sum_inside[0] + sum_outside[1], sum_inside[1] + sum_outside[0]);
                if (er == n) {
                    break;
                }
                sum_inside[0] = sum_inside[1] = sum_outside[0] = sum_outside[1] = 0;
                bl = el;
                br = er;
                ++er;
            }
        }

Yes, I would like to know about solving this problem too. I got TL 16 because of usual tree structure (bad idea when tree looks like a line — so queries would be executed O(N)), but what is right solution?

What we need a data structure that allows to update numbers in a tree and to find the sum of numbers in a subtree. If we do a preorder traversal of the tree, then any subtree will correspond to a segment in that ordering. And a data structure that allows updating numbers and finding segment sums is a Fenwick tree.