CS Academy Round #41: C. Tennis Tournament

problem

トーナメントの配置で$K$番目に強い人がちょうど$M$回勝つようなものをひとつ構成せよ。

solution

一番左に$K$を置くとする。 左から$2^M$番目までは全て$P_i \le K$で$2^M+1$番目は$P_{2^M+1} \gt K$であれば良い。 そのようにする。$O(N)$。

構成は反転$2$回で済むので、とりあえず構成してみて後から確認すると楽。

implementation

#include <algorithm>
#include <cstdio>
#include <numeric>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int main() {
    int n, k, m; scanf("%d%d%d", &n, &k, &m); -- k;
    vector<int> p(1 << n);
    iota(whole(p), 0);
    reverse(p.begin(), p.begin() + (k + 1));
    reverse(p.begin() + (1 << m), p.end());
    vector<int> cnt(1 << n);
    for (vector<int> q = p; q.size() >= 2; ) {
        vector<int> r;
        for (int i = 0; i < q.size(); i += 2) {
            r.push_back(max(q[i], q[i + 1]));
            cnt[r.back()] += 1;
        }
        q = r;
    }
    if (cnt[k] != m) {
        p.clear();
        printf("-1\n");
    } else {
        repeat (i, p.size()) {
            printf("%d%c", p[i] + 1, i + 1 == p.size() ? '\n' : ' ');
        }
    }
    return 0;
}