Submission #769382

#	Time	Username	Problem	Language	Result	Execution time	Memory
769382		sraeli	Archery (IOI09_archery)	C11	0 / 100	2091 ms	13296 KiB

archery

#include <stdio.h>
#include <assert.h>
#include <string.h>

#define MAX_N 250000
#define MAX_M 1000000000

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

typedef struct {
    int first;
    int second;
} Pair;

Pair cache[MAX_N];
int cached[MAX_N];
int black[3 * MAX_N + 1], grey[3 * MAX_N + 1], white[3 * MAX_N + 1];

Pair simulate(int start)
{
    int targ = start >> 1;
    if (cached[targ])
        return cache[targ];

    if (rank == 1) {
        cache[targ].first = 1;
        cache[targ].second = 0;
    } else if (rank <= n + 1) {
        memset(black, 0, sizeof(black));
        memset(grey, 0, sizeof(grey));
        memset(white, 0, sizeof(white));

        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]++;
        }

        int archer1, archer2;
        if (start < 2) {
            archer1 = ranks[1];
            archer2 = rank;
        } else {
            archer1 = ranks[1];
            archer2 = ranks[2];
        }

        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++) {
            if (round % n == 0) {
                int cur_target = round / n;
                int next_target = (cur_target + 1) % n;

                cumulative_black += black[cur_target];
                cumulative_grey += grey[cur_target];
                cumulative_white += white[cur_target];

                black[next_target] = cumulative_black;
                grey[next_target] = cumulative_grey;
                white[next_target] = cumulative_white;

                cumulative_black = cumulative_grey = cumulative_white = 0;
            }

            if (round % n == 0 && round > 0) {
                int cur_target = round / n;
                int prev_target = (cur_target - 1 + n) % n;

                if (black[prev_target] >= s_black && grey[prev_target] >= s_grey && white[prev_target] >= s_white) {
                    bumps++;
                    if (seen == -1)
                        seen = round;
                }
            }
        }

        int final_position = (start + m) % (2 * n);

        if (final_position == 0 && seen != -1) {
            int remaining_rounds = m - seen;
            int num_cycles = remaining_rounds / (3 * n);
            int remaining = remaining_rounds % (3 * n);

            final_position = num_cycles * n + remaining;

            if (remaining < seen)
                final_position = final_position + n;
        } else if (final_position > 0 && final_position <= n) {
            int cur_target = (final_position - 1) / n;
            final_position += bumps;
            final_position += cumulative_black;
            final_position += cumulative_grey;
            final_position += cumulative_white;
            final_position -= black[cur_target];
        }

        cache[targ].first = final_position;
        cache[targ].second = bumps;
        cached[targ] = 1;

        return cache[targ];
    } else {
        cache[targ].first = n + 1;
        cache[targ].second = 0;
        cached[targ] = 1;
        return cache[targ];
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    assert(2 <= n && n <= MAX_N);
    assert(0 <= m && m <= MAX_M);

    for (int i = 1; i <= n * 2; i++) {
        scanf("%d", &ranks[i]);
        assert(1 <= ranks[i] && ranks[i] <= n * 2);
    }

    for (rank = 1; rank <= n * 2; rank++) {
        int start = rank - 1;
        Pair result = simulate(start);
        printf("%d %d\n", result.first, result.second);
    }

    return 0;
}

Compilation message (stderr)

archery.c: In function 'simulate':
archery.c:130:1: warning: control reaches end of non-void function [-Wreturn-type]
  130 | }
      | ^
archery.c: In function 'main':
archery.c:134:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     scanf("%d %d", &n, &m);
      |     ^~~~~~~~~~~~~~~~~~~~~~
archery.c:139:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         scanf("%d", &ranks[i]);
      |         ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 94