| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 769382 |
2023-06-29T13:36:53 Z |
sraeli |
Archery (IOI09_archery) |
C |
|
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]);
| ^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
