oj.uz

답안 #769382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769382 2023-06-29T13:36:53 Z sraeli Archery (IOI09_archery) C
0 / 100
 2000 ms 13296 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()
{
    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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9044 KB Output isn't correct
2 Incorrect 159 ms 9128 KB Output isn't correct
3 Incorrect 12 ms 9044 KB Output isn't correct
4 Incorrect 245 ms 9148 KB Output isn't correct
5 Incorrect 5 ms 9044 KB Output isn't correct
6 Incorrect 25 ms 9116 KB Output isn't correct

Subtask #2
0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9000 KB Output isn't correct
2 Incorrect 20 ms 9044 KB Output isn't correct
3 Incorrect 133 ms 9132 KB Output isn't correct
4 Execution timed out 2087 ms 9640 KB Time limit exceeded
5 Execution timed out 2079 ms 12656 KB Time limit exceeded
6 Incorrect 21 ms 9044 KB Output isn't correct
7 Incorrect 82 ms 9120 KB Output isn't correct
8 Execution timed out 2066 ms 9536 KB Time limit exceeded
9 Execution timed out 2082 ms 9516 KB Time limit exceeded
10 Incorrect 106 ms 9124 KB Output isn't correct
11 Execution timed out 2089 ms 9524 KB Time limit exceeded
12 Incorrect 274 ms 9152 KB Output isn't correct
13 Execution timed out 2088 ms 11764 KB Time limit exceeded
14 Incorrect 595 ms 9308 KB Output isn't correct
15 Execution timed out 2085 ms 9852 KB Time limit exceeded
16 Incorrect 21 ms 9044 KB Output isn't correct
17 Incorrect 119 ms 9124 KB Output isn't correct
18 Incorrect 201 ms 9268 KB Output isn't correct
19 Incorrect 396 ms 9164 KB Output isn't correct
20 Incorrect 611 ms 9292 KB Output isn't correct
21 Execution timed out 2073 ms 9656 KB Time limit exceeded
22 Execution timed out 2091 ms 9812 KB Time limit exceeded
23 Execution timed out 2072 ms 12900 KB Time limit exceeded
24 Incorrect 20 ms 9000 KB Output isn't correct
25 Incorrect 91 ms 9120 KB Output isn't correct
26 Incorrect 605 ms 9228 KB Output isn't correct
27 Execution timed out 2082 ms 9596 KB Time limit exceeded
28 Execution timed out 2065 ms 11836 KB Time limit exceeded
29 Incorrect 136 ms 9124 KB Output isn't correct
30 Incorrect 618 ms 9308 KB Output isn't correct
31 Execution timed out 2059 ms 9624 KB Time limit exceeded
32 Execution timed out 2073 ms 12768 KB Time limit exceeded
33 Incorrect 21 ms 9044 KB Output isn't correct
34 Incorrect 20 ms 9044 KB Output isn't correct
35 Incorrect 214 ms 9276 KB Output isn't correct
36 Incorrect 259 ms 9124 KB Output isn't correct
37 Execution timed out 2036 ms 9544 KB Time limit exceeded
38 Execution timed out 2071 ms 9764 KB Time limit exceeded
39 Incorrect 19 ms 9044 KB Output isn't correct
40 Incorrect 93 ms 9240 KB Output isn't correct
41 Incorrect 200 ms 9152 KB Output isn't correct
42 Incorrect 245 ms 9156 KB Output isn't correct
43 Incorrect 588 ms 9304 KB Output isn't correct
44 Incorrect 1654 ms 9548 KB Output isn't correct
45 Execution timed out 2068 ms 9768 KB Time limit exceeded
46 Execution timed out 2070 ms 9720 KB Time limit exceeded
47 Execution timed out 2080 ms 13296 KB Time limit exceeded