답안 #205619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205619 2020-02-29T10:23:15 Z model_code Archery (IOI09_archery) C++17
100 / 100
374 ms 11128 KB
/**
 * Solution to IOI 2009 problem "archery"
 *
 * An O(NlogN) solution.
 *
 * Carl Hultquist, [email protected]
 */

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

#define rank _adkasndkadjnsjk

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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 31 ms 9336 KB Output is correct
4 Correct 47 ms 9464 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 9336 KB Output is correct
2 Correct 32 ms 9336 KB Output is correct
3 Correct 45 ms 9336 KB Output is correct
4 Correct 82 ms 9592 KB Output is correct
5 Correct 374 ms 10872 KB Output is correct
6 Correct 33 ms 9464 KB Output is correct
7 Correct 23 ms 9464 KB Output is correct
8 Correct 41 ms 9464 KB Output is correct
9 Correct 79 ms 9592 KB Output is correct
10 Correct 23 ms 9336 KB Output is correct
11 Correct 83 ms 9848 KB Output is correct
12 Correct 45 ms 9464 KB Output is correct
13 Correct 223 ms 10616 KB Output is correct
14 Correct 49 ms 9464 KB Output is correct
15 Correct 94 ms 9720 KB Output is correct
16 Correct 31 ms 9336 KB Output is correct
17 Correct 45 ms 9336 KB Output is correct
18 Correct 44 ms 9464 KB Output is correct
19 Correct 47 ms 9464 KB Output is correct
20 Correct 50 ms 9464 KB Output is correct
21 Correct 75 ms 9596 KB Output is correct
22 Correct 95 ms 9720 KB Output is correct
23 Correct 317 ms 11128 KB Output is correct
24 Correct 5 ms 632 KB Output is correct
25 Correct 6 ms 632 KB Output is correct
26 Correct 11 ms 632 KB Output is correct
27 Correct 35 ms 888 KB Output is correct
28 Correct 212 ms 2616 KB Output is correct
29 Correct 6 ms 632 KB Output is correct
30 Correct 10 ms 632 KB Output is correct
31 Correct 29 ms 1016 KB Output is correct
32 Correct 257 ms 3460 KB Output is correct
33 Correct 5 ms 504 KB Output is correct
34 Correct 5 ms 632 KB Output is correct
35 Correct 7 ms 632 KB Output is correct
36 Correct 7 ms 632 KB Output is correct
37 Correct 27 ms 888 KB Output is correct
38 Correct 34 ms 1016 KB Output is correct
39 Correct 5 ms 632 KB Output is correct
40 Correct 6 ms 632 KB Output is correct
41 Correct 7 ms 760 KB Output is correct
42 Correct 7 ms 632 KB Output is correct
43 Correct 11 ms 760 KB Output is correct
44 Correct 17 ms 760 KB Output is correct
45 Correct 29 ms 888 KB Output is correct
46 Correct 32 ms 1016 KB Output is correct
47 Correct 289 ms 3900 KB Output is correct