http://cms.ioi-jp.org/contest/

In my pc Ioi function was returning 0 (I didn't change anything), but grader accepted it correct for sample case..

And one thing, I wrote Move(0) at beginning of Ioi function, grader gave me Wrong Answer[6], however, it is written when calling Move(x) x should be in range 0 to n-1 (inclusive).

Following code gives AC

Joi.cpp

#include "Joi.h"

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i = 0; i < 60; i++) MessageBoard(i, !!(X&(1ll<<i)));
	for(int i = 60; i < N; i++) MessageBoard(i, !!(i&1));
}

Ioi.cpp

#include "Ioi.h"
typedef long long ll;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	ll ret = 0;
	for(int i = 0; i < 60; i++) ret += (ll)Move(i)<<i;
	return ret;
}

I didn'tt know how to make less than 180 moves when depth is less then 60, so my code didn't get 100 but when I go to the root immediately it takes 100.

// while(P != 1) {
    // Move(par[P] - 1);
    // P = par[P];
// }
    Move(0);

That's really a issue :(

kriii figured out why. This is the official grader code.

static bool HasEdge(int u, int v)
{
    if (u > v) swap(u, v);
    return lower_bound(edges, edges + M, make_pair(u, v));
}

That is a code which g++ might optimize to return true....

A slow solution to B: (I hope this makes sense)

Let L1 and L2 be the lines between which the bulldozer will dig. Given a line k, how do we find the optimal choice of L1, L2, such that L1, L2 are parallel to k? Note that k orders the n points (if k is parallel to some line between two points, then these points will occupy the same spot in the ordering, but we don't need to consider such lines k), and that the points between L1 and L2 will occupy a contiguous subsegment in this order. So we just need to find the maximal segment-sum a[l]+...+a[r] in the array a[0],...,a[n-1] where a[i] is the value of the i:th rock in the ordering induced by k.

Now imagine rotating k: Usually, the order of the points does not change. In fact, the order changes precisely when k is parallel to a line between two or more points; then the order of all the points on that line is reversed. So if we can precompute these lines, (and order them by angle), we can simulate the rotation of k and update the order.

Now we just need to find the maximum segment-sum after each update of the order. We can actually handle arbitary changes to a[i] using a segment tree: Let each node keep track of the sum of its segment, the maximum and minimum prefix sums of the segment, and the maximum segment-sum contained in its segment.

Anyway, the complexity is O(n^2*log n), which is pretty slow: I got TLE on all subtasks except the first 2 :(. But I think this might have passed if I optimized it more.

You can submit 'Bulldozer' and 'Golf' here. 'Amusement Park' will be available in 12 hours, I think.

OK OK,this page has been updated and we can get Problem Statements,Reviews and Test Data.