Submission #769662

#	Time	Username	Problem	Language	Result	Execution time	Memory
769662		sraeli	Archery (IOI09_archery)	C11	Compilation error	0 ms	0 KiB

archery

#include <iostream>
#include <cassert>
#include <cstring>
#include <utility>

using namespace std;

#define MAX_N 250000
#define MAX_M 1000000000

int n, m;
int ranks[MAX_N * 2];
int rank;

pair<int, int> cache[MAX_N];
bool cached[MAX_N];
int black[3 * MAX_N + 1], grey[3 * MAX_N + 1], white[3 * MAX_N + 1];

/**
 * An O(N) simulation of the tournament, given our starting
 * position. We also return the number of times that the
 * we get bumped from target 1 to target N.
 */
pair<int, int> simulate(int start)
{
    // As we might run multiple binary searches, we cache
    // the output from this routine for efficiency.
    int targ = start >> 1;
    if (cached[targ])
        return cache[targ];

    if (rank == 1)
        cache[targ] = make_pair(1, 0);
    else if (rank <= n + 1)
    {
        // We're part of the group of archers that circles
        // around after 2*N rounds. To find out where we
        // will finish after M rounds, we only consider what
        // happens on target 1. After 2*N rounds have taken
        // place, we note the next round at which we compete
        // on target 1 -- we can then easily compute where
        // we will finish, since for each successive round
        // we will move to the next target (as we'll be in
        // the cycle phase).

        memset(black, 0, sizeof(black));
        memset(grey, 0, sizeof(grey));
        memset(white, 0, sizeof(white));

        // Update the initial p values of the archers -- this is the
        // minimum number of rounds that it will take an archer to
        // reach the first target.
        grey[start >> 1] = 1;
        for (int i = 1; i < n * 2; i++)
        {
            int target = (i - 1 + (i > start ? 1 : 0)) >> 1;
            if (ranks[i] < rank)
                black[target]++;
            else
                white[target]++;
        }

        // Work out the ranks of the first two archers on the first target
        int archer1, archer2;
        if (start < 2)
        {
            archer1 = ranks[1];
            archer2 = rank;
        }
        else {
            archer1 = ranks[1];
            archer2 = ranks[2];
        }

        // And convert the ranks into counts of black, grey and white
        // archers.
        int s_black = 0, s_grey = 0, s_white = 0;
        if (archer1 < rank)
            s_black++;
        else if (archer1 == rank)
            s_grey++;
        else
            s_white++;
        if (archer2 < rank)
            s_black++;
        else if (archer2 == rank)
            s_grey++;
        else
            s_white++;

        int cumulative_black = 0, cumulative_grey = 0, cumulative_white = 0;
        int seen = -1;
        int bumps = 0;

        for (int round = 0; round < 3 * n; round++)
        {
            // Check if we've seen ourselves on target 1 after
            // enough rounds have passed.
            if (round >= 2 * n && (s_grey == 1))
            {
                seen = round;
                break;
            }

            // Determine the colour of the loser of this round
            int loser;
            if (s_black > 0)
            {
                if (s_black == 2)
                    loser = 0;
                else if (s_grey == 1)
                {
                    loser = 1;
                    bumps++;
                }
                else
                    loser = 2;
            }
            else
                loser = 2;

            // We expect the loser to make it back to the first target n
            // rounds from now at best (if they win all of their matches).
            int new_p = round + n;
            if (new_p <= 3 * n)
            {
                // We only consider cases below 3n, since that is as far
                // as we need to simulate.

                if (loser == 0)
                {
                    black[new_p]++;
                    s_black--;
                }
                else if (loser == 1)
                {
                    grey[new_p]++;
                    s_grey--;
                }
                else
                {
                    white[new_p]++;
                    s_white--;
                }
            }

            // Now pick an archer to move onto target 1. We add to our
            // consideration list all of the archers who we thought would
            // make it by the coming round.
            cumulative_black += black[round + 1];
            cumulative_grey += grey[round + 1];
            cumulative_white += white[round + 1];

            // Now pick the best archer out of our consideration
            // list.
            if (cumulative_black > 0)
            {
                s_black++;
                cumulative_black--;
            }
            else if (cumulative_grey > 0)
            {
                s_grey++;
                cumulative_grey--;
            }
            else
            {
                s_white++;
                cumulative_white--;
            }
        }

        if (m > seen)
            bumps++;

        cache[targ] = make_pair(n - ((m - seen + n - 1) % n), bumps);
    }
    else {
        // We're part of the group of weak archers that
        // gets stuck on some target after 2*N rounds. We
        // just need to work out what that target is.
        //
        // The idea is that as we simulate the tournament, we can only
        // end up with at most one weak archer on any target. So to
        // work out where we end up, we "push" the weaker archers around
        // the targets. Specifically, we only push ourself (the grey
        // archer) and all the archers weaker than us (white archers).

        // Keep track of the number of grey and white archers on each
        // target.
        int white[n], grey[n];
        memset(white, 0, sizeof(white));
        memset(grey, 0, sizeof(grey));

        grey[start >> 1] = 1;

        for (int i = 1; i < 2 * n; i++)
            if (ranks[i] > rank)
                white[(i - 1 + (i > start ? 1 : 0)) >> 1]++;

        // Now we push them around. We start at the first target and follow
        // the targets that archers would get moved to for losing on each
        // target, keeping track of how many archers we are pushing around.
        int shift_white = 0, shift_grey = 0;
        int bumps = 0;

        // It should take 2n rounds for the archers to settle. However, we
        // will only pick up some of the archers towards the end of our first
        // round, so we run for 3n rounds to accommodate this.
        for (int it = 0; it < 3; it++)
        {
            // Start at the first target
            int pos = 0;
            do {
                // Calculate the total number of archers we have on this
                // target, including the ones that we've pushed from the
                // previous target.
                int cur_white = white[pos] + shift_white;
                int cur_grey = grey[pos] + shift_grey;

                // Now leave an archer behind and work out how many we
                // should push to the next target.
                if (cur_white + cur_grey > 1)
                {
                    // More than one grey + white archer, so we must
                    // leave one behind and push the others.
                    if (pos > 0)
                    {
                        // If this is not the first target, then the
                        // grey archer advances, if present, and a
                        // white one stays.
                        white[pos] = 1;
                        shift_white = cur_white - 1;
                        grey[pos] = 0;
                        if (cur_grey > 0)
                            shift_grey = cur_grey;
                        else
                            shift_grey = 0;
                    }
                    else {
                        // If this is the first target, then the grey
                        // one stays (if present) and the white ones
                        // get pushed.
                        if (cur_grey > 0)
                        {
                            grey[pos] = 1;
                            white[pos] = 0;
                            shift_grey = cur_grey - 1;
                            shift_white = cur_white;
                        }
                        else
                        {
                            grey[pos] = 0;
                            white[pos] = 1;
                            shift_grey = 0;
                            shift_white = cur_white - 1;
                        }
                    }
                }
                else {
                    // Only one white or grey archer, so either leave
                    // them behind or push them depending on which target
                    // we are on.
                    if (pos > 0)
                    {
                        white[pos] = cur_white;
                        grey[pos] = cur_grey;
                        shift_white = 0;
                        shift_grey = 0;
                    }
                    else
                    {
                        if (cur_grey > 0)
                            bumps++;
                        white[pos] = 0;
                        grey[pos] = 0;
                        shift_white = cur_white;
                        shift_grey = cur_grey;
                    }
                }

                // Move onto the next position.
                if (pos == 0)
                    pos = n - 1;
                else
                    pos--;
            } while (pos > 0);
        }

        int i;
        for (i = 0; i < n; i++)
            if (grey[i] > 0)
            {
                cache[targ] = make_pair(i + 1, bumps);
                break;
            }

        // Sanity check
        assert(i < n && grey[i] > 0);
    }

    cached[targ] = 1;
    return cache[targ];
}

/**
 * Binary search for the best place to start within a given range
 * of starting positions. This assumes that our ending position will
 * not wrap as we try different starting positions; see the main
 * method below for details of how this is used.
 */
pair<int, int> search(int s, int e)
{
    pair<int, int> start, end, mid;
    int mi;
    start = simulate(s * 2 - 1);
    end = simulate(e * 2 - 1);
    while ((e - s) > 1)
    {
        mi = (s + e) >> 1;
        mid = simulate(mi * 2 - 1);

        if (start.first < mid.first)
        {
            e = mi;
            end = mid;
        }
        else {
            s = mi;
            start = mid;
        }
    }

    if (start.first < end.first)
        return make_pair(start.first, s);
    else
        return make_pair(end.first, e);
}

int main()
{
    memset(cached, 0, sizeof(cached));

    cin >> n >> m;
    assert(1 <= n && n <= MAX_N);
    assert(2 * n <= m && m <= MAX_M);

    //  We reduce m to take advantage of the fact that after
    // 2n rounds, the archers move around in a cyclical pattern.
    m = 2 * n + (m % n);

    for (int i = 0; i < n * 2; i++)
        cin >> ranks[i];

    rank = ranks[0];

    // We binary search to find the target to start at. To do this,
    // we may require two searches (one to find the point at which
    // we wrap around to the next target, and one to then find the
    // best target).
    int best_start;
    pair<int, int> start, end, mid;
    int s = 1, e = n, mi;
    start = simulate(s * 2 - 1);
    end = simulate(e * 2 - 1);
    if (start.second > end.second)
    {
        // There's a wrap. Start by finding the wrapping point.
        while ((e - s) > 1)
        {
            mi = (s + e) >> 1;
            mid = simulate(mi * 2 - 1);

            if (mid.second > end.second)
            {
                // We've wrapped, and so have gone too far.
                s = mi;
                start = mid;
            }
            else
            {
                // No wrap yet. Better push it a bit further.
                e = mi;
                end = mid;
            }
        }

        if (start.second > end.second)
            mi = e;
        else
            mi = s;

        pair<int, int> start_side = search(1, mi - 1);
        pair<int, int> end_side = search(mi, n);

        if (start_side.first < end_side.first)
            best_start = start_side.second;
        else
            best_start = end_side.second;
    }
    else
    {
        // No wrap, just binary search for the best place to
        // start.
        pair<int, int> best = search(1, n);
        best_start = best.second;
    }

    cout << best_start << endl;

    return 0;
}

Compilation message (stderr)

archery.c:1:10: fatal error: iostream: No such file or directory
    1 | #include <iostream>
      |          ^~~~~~~~~~
compilation terminated.