Solution

首先，这里输入很奇葩。我们可以把它拆成一个序列，设序列长度为 $N=n\times m$。

假设 $A_{N-1}+2 \leq A_N$。可以证明，Xuan 总是会获胜。

• 如果 Xuan 能够使得 $A_N<A_{N-1}$ 并让 Xiang 面对一个必输的局面，Xuan 就会赢。
• 假设通过使 $a_N<a_{N-1}$ 能够获得所有必胜的局面。然后，如果我们 $a_N \gets a_{N-1}+1$，那么可以从该局面过渡到的所有局面都是必胜的。因此，将 $a_N \gets a_{N-1}+1$ 所得到的局面是必败的。所以，初始局面是必胜的。

接下来，考虑当给定一个满足 $a_N=a_{N-1}+1$ 的局面。根据上述证明，Xuan 和 Xiang 不应该给出最大两个元素差为 $2$ 或更大的局面。综上，我们可以假设 $a$ 的最大两个元素的差为 $1$。

然后，我们发现每一步操作都会将 $\max\{a\}$ 减少 $1$。

当 $\max\{a\}=N-1$ 时，该局面无法进行操作，因此可以根据输入中 $a_N$ 和 $N-1$ 的奇偶性差异来确定赢家。

复杂度为 $O(N)$。

但是输入不是有序，进行排序。复杂度为 $O(N \log N)$。

std 和这里的说法有些不同，std 写法更为简洁。

Code

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[300020];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n * m; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n * m + 1);
    for (int i = 1; i <= n * m; i++)
    {
        a[i] -= i - 1;
    }
    if (a[n * m] == a[n * m - 1] && (a[n * m] % 2 == 0))
        puts("Xiang");
    else
        puts("Xuan");
    return 0;
}