CS Academy Round41 Tennis Tournament

题目链接：https://csacademy.com/contest/archive/task/tennis-tournament

题目大意：N个人在比赛，每个人编号1到N，N为2的幂，编号大的人获胜。问想要让第K个人在被击败之前胜利M场是否可行，若可行，输出一种方案。

解题思路：比赛过程就是个完美二叉树。首先，如果K的二进制位数-1 比M小则无可行方案；如果K为N，那么M必须为N的二进制位数-1，从大到小即为一种可行方案，否则不可行；如果M为0，那直接让K与N安排第一场比赛，其余无所谓；

接下来，考虑K，K-1与N，想要K胜利M场，只要让K在第M场获胜，第M+1场与N比赛即可。要让K在第M场获胜，让K-1与K在第M-1场比，然后会发现实际上这非常简单。只要让K与K-1的前M-1场比赛的人都比K-1小即可，而由于K的二进制为-1大于等于M，因此这又一定是可行的，然后再让N在第M+1场与K比较即可。

然而比赛的时候想当然了。。。

代码：

 1 const int maxn = 1e6 + 5;
 2 int perm[maxn], vis[maxn];
 3 int n, m, k;
 4 
 5 int main(){
 6     scanf("%d %d %d", &n, &k, &m);
 7     n = 1 << n;
 8     memset(vis, 0, sizeof(vis));
 9     int xk = 0, tmk = k;
10     while(tmk) {
11         tmk >>= 1; xk++;
12     }
13     xk -= 1;
14     if(xk < m || (k == n && m < xk)) {
15         printf("-1");
16         return 0;
17     }
18     else if(m == 0){
19         perm[1] = k; perm[2] = n;
20         vis[k] = vis[n] = 1;
21     }
22     else if(k == n){
23         for(int i = n; i >= 1; i--) {
24             printf("%d", i);
25             if(i != 1) printf(" ");
26         }
27         return 0;
28     }
29     else{
30         int inter = 1 << (m - 1);
31         perm[1] = n; perm[inter * 2 + 1] = k; perm[inter * 3 + 1] = k - 1;
32         vis[n] = vis[k] = vis[k - 1] = 1;
33         int st = inter * 2 + 1, ed = st + inter * 2 - 1;
34         int j = 1;
35         for(int i = st; i <= ed; i++){
36             if(perm[i] == 0) {
37                 while(vis[j]) j++;
38                 perm[i] = j;
39                 vis[j] = 1;
40             }
41         }
42         j = 1;
43         for(int i = 1; i <= n; i++){
44             if(perm[i] == 0){
45                 while(vis[j]) j++;
46                 perm[i] = j;
47                 vis[j] = 1;
48             }
49         }
50     }
51     int j = 1;
52     for(int i = n; i >= 1; i--){
53         while(vis[j]) j++;
54         if(perm[i] == 0) {
55             perm[i] = j;
56             vis[j] = 1;
57         }
58     }
59     for(int i = 1; i <= n; i++){
60         printf("%d", perm[i]);
61         if(i != n) printf(" ");
62     }
63 }

题目：

Tennis Tournament

Time limit: 1000 ms
Memory limit: 128 MB

There are $2^N2N players that are going to take part in a tennis tournament. Each player ii has a skill level equal to ii. When two people play against each other, the one with a higher skill level will always win.$

Before the tennis tournament, the players will be permuted in a certain way. In the first round, matches will be played between $P_1P1 and P_2P2, P_3P3 and P_4P4, and so on, where P_iPi is the i^{th}ith player in the permutation.$

In the second round, the winner of the first match from the previous round will face the winner of the second match. The winner of the third match will face the winner of the fourth match, and so on. In the final, the best player from the first half of the permutation will play against the best player from the second half.

Given two integers

Standard input

The first line contains three integers

Standard output

If there is no solution output

Otherwise, print the permutation on the first line.

Constraints and notes

$2^N1≤K≤2N$

Input	Output	Explanation
2 2 0	2 4 1 3	2441334
2 2 1	4 3 2 1	4432214
2 4 2	2 3 1 4	2331444
3 6 2	5 4 1 6 7 8 3 2	541678325683688
3 6 1	8 5 2 6 3 7 1 4	852637148673878
2 1 1	-1	There is no way that player 1 can win a game, since he loses against all other players.