C - ABC Tournament Editorial by QCFium


解法 1

トーナメントをそのままシミュレートします。
問題文のトーナメントの正確な定義に従って処理をします。

解答例 (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[0] == next_remaining[0] ? remaining[1] : remaining[0]));
			return 0;
		}
		remaining = next_remaining;
	}
	
	return 0;
}

解法 2

準優勝するのは、優勝する( = 一番レートが高い) 選手とは逆側のブロックにいる選手のうち一番レートが高い人です。
こちらは解法 1より実装がかなり楽です。

解答例 (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: