abc188_c - Abc Tournament
10 Jan 2021 — Tags: implementation,observation,greedy — URLThe two finalist will be the ones that have maximum rating in both halves of the tournament.
Time complexity: $O(2^n)$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
n = (1LL << n);
ii ansl = {0, 0}, ansr = {0, 0};
for (int i = 0; i < n / 2; ++i)
{
int ai;
cin >> ai;
ansl = max(ansl, {ai, i});
}
for (int i = n / 2; i < n; ++i)
{
int ai;
cin >> ai;
ansr = max(ansr, {ai, i});
}
ii ans = min(ansl, ansr);
cout << ans.second + 1 << endl;
return 0;
}