Submission #769384

#	Time	Username	Problem	Language	Result	Execution time	Memory
769384		sraeli	Archery (IOI09_archery)	C11	0 / 100	2092 ms	10780 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()
{
   if (scanf("%d %d", &n, &m) != 2) {
    printf("Erro ao ler os valores de entrada.\n");
    return 1;
}

    assert(2 <= n && n <= MAX_N);
    assert(0 <= m && m <= MAX_M);
 
    for (int i = 1; i <= n * 2; i++) {
        if (scanf("%d", &ranks[i]) != 1) {
    printf("Erro ao ler os valores de entrada.\n");
    return 1;
}
        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 | }
      | ^

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