oj.uz

Submission #769384

# Submission time Handle Problem Language Result Execution time Memory
769384 2023-06-29T13:41:06 Z sraeli Archery (IOI09_archery) C
0 / 100
 2000 ms 10780 KB 
#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

archery.c: In function 'simulate':
archery.c:130:1: warning: control reaches end of non-void function [-Wreturn-type]
  130 | }
      | ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9044 KB Output isn't correct
2 Incorrect 188 ms 9116 KB Output isn't correct
3 Incorrect 12 ms 9044 KB Output isn't correct
4 Incorrect 290 ms 9124 KB Output isn't correct
5 Incorrect 5 ms 9112 KB Output isn't correct
6 Incorrect 22 ms 9112 KB Output isn't correct

Subtask #2
0 / 94.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9112 KB Output isn't correct
2 Incorrect 22 ms 9112 KB Output isn't correct
3 Incorrect 152 ms 9112 KB Output isn't correct
4 Execution timed out 2067 ms 9372 KB Time limit exceeded
5 Execution timed out 2068 ms 10432 KB Time limit exceeded
6 Incorrect 19 ms 9116 KB Output isn't correct
7 Incorrect 98 ms 9112 KB Output isn't correct
8 Execution timed out 2092 ms 9308 KB Time limit exceeded
9 Execution timed out 2049 ms 9412 KB Time limit exceeded
10 Incorrect 105 ms 9124 KB Output isn't correct
11 Execution timed out 2088 ms 9352 KB Time limit exceeded
12 Incorrect 271 ms 9116 KB Output isn't correct
13 Execution timed out 2087 ms 10052 KB Time limit exceeded
14 Incorrect 651 ms 9260 KB Output isn't correct
15 Execution timed out 2079 ms 9412 KB Time limit exceeded
16 Incorrect 19 ms 9112 KB Output isn't correct
17 Incorrect 151 ms 9100 KB Output isn't correct
18 Incorrect 223 ms 9108 KB Output isn't correct
19 Incorrect 441 ms 9124 KB Output isn't correct
20 Incorrect 717 ms 9144 KB Output isn't correct
21 Execution timed out 2083 ms 9304 KB Time limit exceeded
22 Execution timed out 2081 ms 9368 KB Time limit exceeded
23 Execution timed out 2091 ms 10504 KB Time limit exceeded
24 Incorrect 20 ms 9044 KB Output isn't correct
25 Incorrect 108 ms 9096 KB Output isn't correct
26 Incorrect 681 ms 9264 KB Output isn't correct
27 Execution timed out 2080 ms 9344 KB Time limit exceeded
28 Execution timed out 2087 ms 10096 KB Time limit exceeded
29 Incorrect 174 ms 9108 KB Output isn't correct
30 Incorrect 631 ms 9264 KB Output isn't correct
31 Execution timed out 2055 ms 9392 KB Time limit exceeded
32 Execution timed out 2084 ms 10468 KB Time limit exceeded
33 Incorrect 21 ms 9044 KB Output isn't correct
34 Incorrect 21 ms 9120 KB Output isn't correct
35 Incorrect 206 ms 9116 KB Output isn't correct
36 Incorrect 261 ms 9124 KB Output isn't correct
37 Execution timed out 2077 ms 9392 KB Time limit exceeded
38 Execution timed out 2073 ms 9424 KB Time limit exceeded
39 Incorrect 21 ms 9044 KB Output isn't correct
40 Incorrect 97 ms 9108 KB Output isn't correct
41 Incorrect 214 ms 9120 KB Output isn't correct
42 Incorrect 245 ms 9124 KB Output isn't correct
43 Incorrect 642 ms 9176 KB Output isn't correct
44 Incorrect 1651 ms 9356 KB Output isn't correct
45 Execution timed out 2081 ms 9248 KB Time limit exceeded
46 Execution timed out 2056 ms 9356 KB Time limit exceeded
47 Execution timed out 2071 ms 10780 KB Time limit exceeded