| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 769380 | sraeli | Archery (IOI09_archery) | C11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
/**
* An O(N) simulation of the tournament, given our starting
* position. We also return the number of times that the
* we get bumped from target 1 to target N.
*/
Pair simulate(int start)
{
// As we might run multiple binary searches, we cache
// the output from this routine for efficiency.
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)
{
// We're part of the group of archers that circles
// around after 2*N rounds. To find out where we
// will finish after M rounds, we only consider what
// happens on target 1. After 2*N rounds have taken
// place, we note the next round at which we compete
// on target 1 -- we can then easily compute where
// we will finish, since for each successive round
// we will move to the next target (as we'll be in
// the cycle phase).
memset(black, 0, sizeof(black));
memset(grey, 0, sizeof(grey));
memset(white, 0, sizeof(white));
// Update the initial p values of the archers -- this is the
// minimum number of rounds that it will take an archer to
// reach the first target.
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]++;
}
// Work out the ranks of the first two archers on the first target
int archer1, archer2;
if (start < 2)
{
archer1 = ranks[1];
archer2 = rank;
}
else {
archer1 = ranks[1];
archer2 = ranks[2];
}
// And convert the ranks into counts of black, grey and white
// archers.
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++)
for (int round = 0; round < 3 * n; round++)
{
// Move archers to the next target after each 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;
}
// Check if our archer gets bumped from target 1 to target N
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;
}
}
}
// Calculate the final position after M rounds
int final_position = (start + m) % (2 * n);
// Handle the case where we were bumped from target 1 to target 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 {
// If our rank is higher than n+1, we are always
// eliminated from the tournament after the first round.
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;
}