Contest Duration: - (local time) (100 minutes) Back to Home

## C - ABC Tournament Editorial by en_translator

### Solution 1

Simulate the tournament naively.
During the process, follow the formal definition in the problem statement.

Sample Code (C++)

#include <stdio.h>
#include <utility>
#include <vector>
#include <numeric>

int ri() {
int n;
scanf("%d", &n);
return n;
}

int main() {
int n = ri();
std::vector<int> a(1 << n);
for (auto &i : a) i = ri();

std::vector<int> remaining(1 << n);
std::iota(remaining.begin(), remaining.end(), 0);

for (int i = 1; i <= n; i++) {
std::vector<int> next_remaining;
for (int j = 0; j < 1 << (n - i); j++) {
if (a[remaining[j * 2]] > a[remaining[j * 2 + 1]]) next_remaining.push_back(remaining[j * 2]);
else next_remaining.push_back(remaining[j * 2 + 1]);
}
if (i == n) {
printf("%d\n", 1 + (remaining == next_remaining ? remaining : remaining));
return 0;
}
remaining = next_remaining;
}

return 0;
}



### Solution 2

The player who take the second place has the highest rating in the opposite block where the winner (=the player with the highest rating) belongs. The implementation is fairly easier than Solution 1.

Sample Code (C++)

#include <stdio.h>
#include <utility>
#include <algorithm>
#include <vector>

int ri() {
int n;
scanf("%d", &n);
return n;
}

int main() {
int n = ri();
std::vector<int> a(1 << n);
for (auto &i : a) i = ri();
int half = 1 << (n - 1);
int max = std::max_element(a.begin(), a.end()) - a.begin();
auto start = max < half ? a.begin() + half : a.begin();
printf("%d\n", (int) (std::max_element(start, start + half) - a.begin() + 1));

return 0;
}



posted:
last update: