Znzryb's Blog

ABC-470-C - Inc, Dec, Xor 增减异或（注意题目条件限制：初始时 A 的所有元素均为 0，以及操作的摊还分析）

Posted on 2026-08-10

题目大意

Inc, Dec, Xor

有一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ ，初始时 $A$ 的所有元素均为 $0$ 。

给定 $Q$ 个操作，请按顺序依次处理。操作共有两种，格式如下：

1 x：将 $A_x$ 的值增加 $1$ 。
2：对每个 $i=1,2,\ldots,N$ ，若 $A_i \geq 1$ ，则将 $A_i$ 的值减少 $1$ 。

请求出每次操作处理完毕后 $A_1,A_2,\ldots,A_N$ 的按位异或值。

关于按位异或
非负整数 $A,B$ 的按位异或 $A \oplus B$ 定义如下： $A \oplus B$ 在二进制表示下 $2^k$ （ $k \geq 0$ ）位上的数字，当 $A,B$ 在二进制表示下 $2^k$ 位上的数字恰有一个为 $1$ 时为 $1$ ，否则为 $0$ 。
例如 $3 \oplus 5 = 6$ （二进制表示为 $011 \oplus 101 = 110$ ）。
一般地， $k$ 个非负整数 $p_1,p_2,\ldots,p_k$ 的按位异或定义为 $(\dots((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ ，可以证明其结果与 $p_1,p_2,\ldots,p_k$ 的顺序无关。

输入从标准输入按以下格式给出：

N Q
query_1
query_2
⋮
query_Q

其中每个操作为以下两种格式之一：

1 x

输出 $Q$ 行。

第 $i$ 行（ $1\le i\le Q$ ）输出第 $i$ 个操作处理完毕后 $A_1,A_2,\ldots,A_N$ 的按位异或值。

$1\le N\le 5\times 10^5$
$1\le Q\le 5\times 10^5$
$1\le x\le N$
输入的所有值均为整数

处理第 $1$ 个操作后 $A=(0,1)$ ， $0,1$ 的按位异或为 $1$ ，故第 $1$ 行输出 $1$ 。

处理第 $2$ 个操作后 $A=(0,2)$ ， $0,2$ 的按位异或为 $2$ ，故第 $2$ 行输出 $2$ 。

处理第 $3$ 个操作后 $A=(1,2)$ ， $1,2$ 的按位异或为 $3$ ，故第 $3$ 行输出 $3$ 。

处理第 $4$ 个操作后 $A=(0,1)$ ， $0,1$ 的按位异或为 $1$ ，故第 $4$ 行输出 $1$ 。

处理第 $5$ 个操作后 $A=(0,0)$ ， $0,0$ 的按位异或为 $0$ ，故第 $5$ 行输出 $0$ 。

思路讲解

那么这道题目的关键点就是这个，初始时 $A$ 的所有元素均为 $0$ ，以及我们只能增加一个元素啊，我们只要实时维护一个这个正数的这个集合，遇到操作二暴力遍历就可以解决了。

int main() {
    int n = readInt(), q = readInt();

    /* alive：保存所有满足 A[i] >= 1 的下标，且保证【互不重复】。
     * 维护方式：
     *   - A[x] 由 0 变 1 时 push_back(x)（这是唯一的“从零变非零”时机）
     *   - A[i] 由 1 变 0 时把它从 alive 中删除
     * 因为 A[i] = 0 对异或没有贡献，所以只关心非零元素即可。
     */
    vector<int> alive;
    alive.reserve(min(n, q));   // 非零元素个数不会超过 min(N, 操作1次数)

    int cur = 0;                // cur = A[1] ^ A[2] ^ ... ^ A[n]，实时维护

    while (q--) {
        int op = readInt();

        if (op == 1) {
            /* -------- 操作 1：A[x] += 1 -------- */
            int x = readInt();

            if (A[x] == 0) alive.push_back(x);   // 从 0 变成非零，加入集合（不会重复）

            cur ^= A[x];        // 先把旧值的贡献异或掉（旧值为 0 时是空操作）
            ++A[x];
            cur ^= A[x];        // 再把新值的贡献异或上去
        } else {
            /* -------- 操作 2：所有非零元素 -1 --------
             * 直接遍历 alive 暴力做。单次代价 = |alive|，
             * 而这次操作让 sum(A) 恰好减少 |alive|，
             * 由于 sum(A) 的总增量 <= 操作 1 的次数 <= Q，
             * 所以所有操作 2 的总代价 <= Q，均摊 O(1)。
             */
            int m = 0;                          // m 是“原地压缩”后新数组的长度
            for (int idx : alive) {
                cur ^= A[idx];                  // 去掉旧值贡献
                --A[idx];
                cur ^= A[idx];                  // 加上新值贡献（变成 0 时异或 0，无影响）

                if (A[idx] > 0) alive[m++] = idx;  // 仍非零则保留；归零的自然被覆盖删除
            }
            alive.resize(m);                    // 截断，完成删除
        }

        IO::writeInt(cur);      // 每次操作后输出当前全局异或值
    }

    IO::flushOut();
    return 0;
}

AC代码

https://atcoder.jp/contests/abc470/submissions/78274919

AI 代码

#include <bits/stdc++.h>
using namespace std;

/* ==================== 快速读写 ====================
 * N, Q 达到 5e5，输入输出规模在几 MB 级别，
 * 用 fread / fwrite 缓冲避免 cin/scanf 的常数瓶颈。
 */
namespace IO {
    const int BUF = 1 << 16;
    char ibuf[BUF], *ip1 = ibuf, *ip2 = ibuf;

    inline char gc() {
        if (ip1 == ip2) {                                   // 缓冲区空了就重新填充
            ip2 = (ip1 = ibuf) + fread(ibuf, 1, BUF, stdin);
            if (ip1 == ip2) return EOF;
        }
        return *ip1++;
    }
    // 本题所有数值都是非负整数，不需要处理负号
    inline int readInt() {
        int c = gc(), x = 0;
        while (c < '0' || c > '9') c = gc();                 // 跳过空格 / 换行
        while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
        return x;
    }

    char obuf[BUF], *op = obuf;
    inline void flushOut() { fwrite(obuf, 1, op - obuf, stdout); op = obuf; }
    inline void pc(char c) { if (op == obuf + BUF) flushOut(); *op++ = c; }
    inline void writeInt(int x) {
        char tmp[12]; int len = 0;
        do { tmp[len++] = char('0' + x % 10); x /= 10; } while (x);
        while (len) pc(tmp[--len]);
        pc('\n');
    }
}
using IO::readInt;

int A[500005];              // 当前序列，初始全 0（全局数组默认为 0）

int main() {
    int n = readInt(), q = readInt();

    /* alive：保存所有满足 A[i] >= 1 的下标，且保证【互不重复】。
     * 维护方式：
     *   - A[x] 由 0 变 1 时 push_back(x)（这是唯一的“从零变非零”时机）
     *   - A[i] 由 1 变 0 时把它从 alive 中删除
     * 因为 A[i] = 0 对异或没有贡献，所以只关心非零元素即可。
     */
    vector<int> alive;
    alive.reserve(min(n, q));   // 非零元素个数不会超过 min(N, 操作1次数)

    int cur = 0;                // cur = A[1] ^ A[2] ^ ... ^ A[n]，实时维护

    while (q--) {
        int op = readInt();

        if (op == 1) {
            /* -------- 操作 1：A[x] += 1 -------- */
            int x = readInt();

            if (A[x] == 0) alive.push_back(x);   // 从 0 变成非零，加入集合（不会重复）

            cur ^= A[x];        // 先把旧值的贡献异或掉（旧值为 0 时是空操作）
            ++A[x];
            cur ^= A[x];        // 再把新值的贡献异或上去
        } else {
            /* -------- 操作 2：所有非零元素 -1 --------
             * 直接遍历 alive 暴力做。单次代价 = |alive|，
             * 而这次操作让 sum(A) 恰好减少 |alive|，
             * 由于 sum(A) 的总增量 <= 操作 1 的次数 <= Q，
             * 所以所有操作 2 的总代价 <= Q，均摊 O(1)。
             */
            int m = 0;                          // m 是“原地压缩”后新数组的长度
            for (int idx : alive) {
                cur ^= A[idx];                  // 去掉旧值贡献
                --A[idx];
                cur ^= A[idx];                  // 加上新值贡献（变成 0 时异或 0，无影响）

                if (A[idx] > 0) alive[m++] = idx;  // 仍非零则保留；归零的自然被覆盖删除
            }
            alive.resize(m);                    // 截断，完成删除
        }

        IO::writeInt(cur);      // 每次操作后输出当前全局异或值
    }

    IO::flushOut();
    return 0;
}

源代码

心路历程（WA，TLE，MLE……）

ABC-468-F - Chmax（观察到每步操作都要做只能够说有的时候不生效，然后就可以发现，有的是数字，我们是必须去取的）

Posted on 2026-08-09 Edited on 2026-08-10

题目大意

题目描述

给定正整数 $N$ 和 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$ 。

有三个变量 $x,y,c$ ，初始时 $x=y=c=0$ 。

你需要按 $k=1,2,\ldots,N$ 的顺序，依次执行下列两种操作之一：

操作 $1$ ：若 $x < P_k$ ，则将 $c$ 增加 $1$ ；随后将 $x$ 替换为 $\max(x,P_k)$ 。
操作 $2$ ：若 $y < P_k$ ，则将 $c$ 增加 $1$ ；随后将 $y$ 替换为 $\max(y,P_k)$ 。

求最终 $c$ 的最大可能值。

输入格式

输入从标准输入以如下格式给出：

N

P_1\ P_2\ \ldots\ P_N

输出格式

输出一行一个整数，表示答案。

数据范围

$1\le N\le 5\times 10^5$
$P$ 是 $(1,2,\ldots,N)$ 的一个排列
输入的所有值均为整数

样例

1 2	5 4 3 1 2 5

按如下方式操作可以达到 $c=4$ ：

$k=1$ 时：执行操作 $1$ ，此时 $(x,y,c)=(4,0,1)$ 。
$k=2$ 时：执行操作 $1$ ，此时 $(x,y,c)=(4,0,1)$ 。
$k=3$ 时：执行操作 $2$ ，此时 $(x,y,c)=(4,1,2)$ 。
$k=4$ 时：执行操作 $2$ ，此时 $(x,y,c)=(4,2,3)$ 。
$k=5$ 时：执行操作 $2$ ，此时 $(x,y,c)=(4,5,4)$ 。

无论如何操作都无法使 $c$ 超过 $4$ ，因此输出 $4$ 。

1 2	6 6 5 4 3 2 1

1 2	9 3 6 5 2 7 8 9 1 4

思路讲解

我们不难注意到，这个前缀最大值数组中出现的值，我们必须要选啊，而且不仅仅是必须要选，我们的有一个 X / Y 的上升序列一定就是长这个样！否则就不是很优秀啊。

AC代码

源代码

心路历程（WA，TLE，MLE……）

2026牛客暑期多校 7—— Problem H. Modulo Triples

Posted on 2026-08-08 Edited on 2026-08-10

题目大意

题目描述

给定一个正整数 $N$ 。

你需要将集合 $\{0,1,2,\ldots,3N-1\}$ 划分为 $N$ 个有序三元组 $(x_1,y_1,z_1),(x_2,y_2,z_2),\ldots,(x_N,y_N,z_N)$ 。

这些三元组必须同时满足以下所有条件：

集合 $\{0,1,2,\ldots,3N-1\}$ 中的每个整数在所有三元组中恰好出现一次。等价地说，序列 $x_1,y_1,z_1,x_2,y_2,z_2,\ldots,x_N,y_N,z_N$ 必须是集合 $\{0,1,2,\ldots,3N-1\}$ 的一个排列。
对于每个 $i \in \{1,2,\ldots,N\}$ ，都必须满足 $z_i>0$ 且 $x_i \bmod z_i = y_i$ 。

其中， $a \bmod b$ 表示非负整数 $a$ 除以正整数 $b$ 所得的余数。

可以证明，在给定的数据范围内，对于任意 $N$ 至少存在一种合法的构造。你只需要输出任意一种合法的构造即可。

输入格式

输入仅包含一行一个正整数 $N$ （ $1 \le N \le 2\times 10^5$ ）。

输出格式

输出 $N$ 行。

第 $i$ 行需要包含三个整数 $x_i, y_i, z_i$ ，表示第 $i$ 个有序三元组。

对于每个 $i \in \{1,2,\ldots,N\}$ ，你的输出必须满足 $0 \le x_i, y_i, z_i < 3N$ ， $z_i > 0$ 且 $x_i \bmod z_i = y_i$ 。

此外，输出的序列 $x_1,y_1,z_1,x_2,y_2,z_2,\ldots,x_N,y_N,z_N$ 必须是集合 $\{0,1,2,\ldots,3N-1\}$ 的一个排列。

如果存在多种合法的构造，输出任意一种即可。

样例

1
2
3

5 0 1
7 3 4
8 2 6

样例输出给出了三个有序三元组： $(5,0,1)$ ， $(8,2,6)$ ，以及 $(7,3,4)$ 。

它们分别满足等式： $5 \bmod 1 = 0$ ， $8 \bmod 6 = 2$ ， $7 \bmod 4 = 3$ 。

此外，这些三元组中出现的所有整数恰好为 $0,1,2,3,4,5,6,7,8$ ，这正是集合 $\{0,1,\ldots,3N-1\}$ 中的所有整数。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

2026 杭电暑期多校 5——括号凸包（判断一个凸包是否合法，由于起点和终点相同，因此我们肯定绕了个圈子，我们要判断的是到底绕了几圈？只需要看这个向量的方位角是否可通过循环位移排成递增即可啊）（方位角递增这个性质，可以通过这个枚举顺序实现，就不要通过增加 dp 状态实现）

Posted on 2026-08-08 Edited on 2026-08-10

题目大意

括号凸包

给定二维平面上的 $n$ 个点，所有点互不相同，且不存在三点共线。每个点上写有一个括号，可能是左括号 $\texttt{(}$ ，也可能是右括号 $\texttt{)}$ 。

我们称一个字符串 $S$ 是一个合法括号序列，当且仅当它可以由如下递归规则生成：

空串是一个合法括号序列；
如果 $A$ 是合法括号序列，那么字符串 $\texttt{(}A\texttt{)}$ 也是合法括号序列；
如果 $A$ 和 $B$ 都是合法括号序列，那么 $AB$ 也是合法括号序列。

例如， $\texttt{()}$ ， $\texttt{(())}$ ， $\texttt{()()}$ 都是合法括号序列，而 $\texttt{)(}$ ， $\texttt{(()}$ ， $\texttt{())(}$ 不是合法括号序列。

现在，你需要从给定的点中选出若干个互不相同的点作为顶点，构成一个凸多边形。在本题中，一个由 $m$ 个点 $p_{a_1},p_{a_2},\dots,p_{a_m}$ 构成的多边形被称为凸多边形，当且仅当满足：

$m \ge 3$ ；
这些点按照 $a_1,a_2,\dots,a_m$ 的顺序依次连接，并连接 $a_m$ 与 $a_1$ 后，形成一个简单多边形（即多边形的边仅在相邻边的端点处相交，不相邻边互不相交）；
对于该多边形的每一条边，其余所有顶点都严格位于这条边所在直线的同一侧。

换句话说，所选出的点必须恰好按照它们在自身凸包上的环形顺序排列，并且所有内角都严格小于 $180^\circ$ ，凸多边形上不存在三点共线。

对于一个凸多边形，任选其边界上的一个顶点作为起点，并沿着多边形边界按顺时针或逆时针方向依次遍历所有顶点，最后回到起点前停止。这样可以得到一个长度为 $m$ 的括号序列：若当前顶点上写有左括号，则写下 $\texttt{(}$ ；若当前顶点上写有右括号，则写下 $\texttt{)}$ 。

你的任务是找到包含至少一个左括号的凸多边形，使得对于该多边形上的任意一个写有左括号的顶点，以它作为起点沿多边形边界并以任意方向遍历得到的括号序列都是合法括号序列。请计算满足条件的凸多边形个数，并将结果对 $998244353$ 取模后输出。

第一行包含一个整数 $T$ （ $1 \le T \le 100$ ），表示数据组数。

对于每组数据：

第一行包含一个整数 $n$ （ $1 \le n \le 500$ ），表示点的数量。

接下来 $n$ 行，每行包含三个整数 $x_i, y_i, t_i$ （ $0 \le x_i, y_i \le 10^9$ ， $t_i \in \{0, 1\}$ ），表示第 $i$ 个点的坐标和括号类型。其中 $t_i = 0$ 表示左括号， $t_i = 1$ 表示右括号。

保证每组数据中所有点互不相同，且不存在三点共线。

保证所有数据的 $n$ 之和不超过 $1000$ 。

对于每组数据，输出一行一个整数，表示满足条件的凸多边形方案数对 $998244353$ 取模后的结果。

Plaintext

Plaintext

对于第一组样例： $4$ 个点的坐标形如抛物线 $y=x^2$ ，因此这 $4$ 个点的任意大小大于等于 $3$ 的子集都能构成凸多边形。这四个点的括号类型依次为 $\texttt{(}$ 、 $\texttt{)}$ 、 $\texttt{(}$ 、 $\texttt{)}$ 。若选择全部 $4$ 个点构成凸四边形，其顺时针与逆时针的环形括号序列循环节均为 $\texttt{()()}$ 。无论从第 $1$ 个点（左括号）还是第 $3$ 个点（左括号）出发，按顺时针或逆时针方向生成的字符串均为 $\texttt{()()}$ ，是合法序列。可以证明，选取其他任何 $3$ 个点构成的三角形均因括号数量为奇数而无法满足条件。因此，方案数为 $1$ 。
对于第二组样例：给出 $5$ 个点，括号类型依次为 $\texttt{(}$ 、 $\texttt{(}$ 、 $\texttt{(}$ 、 $\texttt{)}$ 、 $\texttt{)}$ 。经尝试，无法选出任何一个使得“从任意左括号出发、沿任意方向遍历”均产生合法序列的凸多边形。方案数为 $0$ 。
对于第五组样例：只有 $1$ 个点，无法满足构成凸多边形要求的最少顶点数（ $m \ge 3$ ），故方案数为 $0$ 。

思路讲解

首先，题目中有关于括号凸包的表述啊，这个括号串肯定是形如这个 $()()()()...()()$ 这样子的形式啊。

因为每个括号串的第一个字符肯定是这个 $（$ ，最后一个字符肯定是 $）$ ，所有奇数位置必是 $（$ ，这个是因为所有的奇数位置肯定是这个开头（题目中要求每个左括号位置循环移动到开头仍然是合法括号串）。

然后接着就是标题里面的结论啊：

判断一个凸包是否合法，只需要看这个向量的方位角是否可通过循环位移排成递增即可啊，当然前提是不能 3 点共线。

那么这个结论实际上是这样子来的啊：

因为我们最终会绕一圈（起点和终点相同），因此我们其实是在判断，是否多绕了一圈。

这个三点不能共线的规定是用在这个 dp 转移里面的。

dp 状态我们先这样子定义，但是这样子：

vector<vector<ll> > dp(N, vector<ll>(N));
for (int i = 0; i < N; ++i) {
	dp[i][i] = 1;
}

这样子会多计算出来一些东西，最后减掉就行啊。

for (int i = 0; i < N; ++i) {
	ans += dp[i][i];
	ans %= mod;
}
// 减掉多余的东西啊
ans -= SZ(vec_ijs) / 2;
ans -= N;

具体转移的代码：

vector<VecIJ> vec_ijs;
vec_ijs.reserve(N * N);
for (int i = 0; i < SZ(A); ++i) {
	for (int j = 0; j < SZ(A); ++j) {
		if (i == j) continue;
		if (A[i].c != A[j].c) {
			auto diff = A[j].p - A[i].p;
			vec_ijs.push_back({diff, i, j});
		}
	}
}
// 进行极角排序（上面重载过 VecIJ 的比较运算符号）
sort(all(vec_ijs));
// 按照边的方位角方向，进行这个转移
for (auto [_,u,v]: vec_ijs) {
	for (int src = 0; src < N; ++src) {
		dp[src][v] += dp[src][u];
		dp[src][v] %= mod;
	}
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1233&rid=11368

源代码

// teamname: Gospel_rock
/**
 * Problem: 括号凸包
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1233&pid=1003
 * Created: 2026-08-04 20:20:45
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

/*
 * 2026-2-3  增加编译器识别 Real 类型功能
 * 2026-3-19 增加了从斜率式和一般式构造 Line
 * 2026-5-4  几何模板大改（QOJ 784 沉淀）：新增 isqrt / sqrtL、cross 三参数重载、polygonSignedArea，reorder_polygon 整体判向，isConvex 加 strict 参数，新增凸多边形直径旋转卡壳
 * 2026-5-5  Luogu P16223 沉淀：Point 加 id 字段，convex_diameter 加 n <= 2 退化特判，新增 furthest_pair_of_point
 * 2026-5-6  P3187 沉淀：getintersect 加浮点 assert + 显式 (DB) cross，make_convex_hull 加 strict 参数，新增 minimum_rectangle_cover
 * 2026-5-11 几何全面模板化：Point / Line 改 template<class T>，T 自动分流 ll / i128 / DB
 * 2026-5-12 加入了 Circle 类
 * 2026-5-13 加入了 half_plane_cut 和 unique_line_polar_angle_sort，加入了隐式转换和转换方向
 * 2026-5-15 加入了 HullMode
 */

// floor(sqrt(n)), n >= 0；二分 + 防溢出
i128 isqrt(i128 n) {
	if (n <= 0) return 0;
	i128 lo = 0, hi = (i128)2e18; // sqrt(4e36) <= 2e18
	while (lo < hi) {
		i128 mid = lo + (hi - lo + 1) / 2;
		if (mid <= n / mid) lo = mid; // 等价 mid*mid <= n，避免 i128 平方溢出
		else hi = mid - 1;
	}
	return lo;
}

// 统一 sqrt 入口：浮点直接 sqrtl；整数（含 i128）走 isqrt + fraction，避免 (long double) i128 在 n > 2^53 时丢整数精度。
template<typename T>
long double sqrtL(T n) {
	if constexpr (is_floating_point_v<T>) {
		return sqrtl((long double)n);
	} else {
		i128 ni = (i128)n;
		if (ni <= 0) return 0;
		i128 i = isqrt(ni);
		long double id = (long double)i;
		long double rd = (long double)(ni - i * i);
		// sqrt(i^2 + r) = i * sqrt(1 + r/i^2)
		return id * sqrtl(1.0L + rd / (id * id));
	}
}

// x*x 安全平方: 整数升 i128 防溢出 (1000^2 不会溢, 但模板要扛 1e9 量级输入),
// 浮点原样 T*T 不动 (i128 没浮点意义).
template<class T>
auto squared(T x) {
	if constexpr (is_floating_point_v<T>) {
		return x * x;
	} else {
		return (i128)x * (i128)x;
	}
}

template<class T>
int sgn(T x) {
	if (-eps < x && x < eps) return 0;
	return x < 0 ? -1 : 1;
}

template<class T>
struct Point {
	T x, y;
	int id = -1; // 原始下标. -1 表示派生点 (+ - * 等算术结果) 或未赋值, id 无意义

	explicit Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {
	}

	// Point<U> -> Point<T> 隐式 (common_type 单调升档方向, U -> T 必须无损):
	// common_type_t<U, T> == T 才放行 (例 ll -> DB 通; DB -> ll 拦, 防 truncation)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	Point(const Point<U> &o) : x((T)o.x), y((T)o.y), id(o.id) {
	}

	// 只对左值生效的复合运算符
	Point &operator+=(Point p) & {
		x += p.x, y += p.y;
		return *this;
	}

	Point &operator-=(Point p) & {
		x -= p.x, y -= p.y;
		return *this;
	}

	Point &operator*=(T t) & {
		x *= t, y *= t;
		return *this;
	}

	Point &operator/=(T t) & {
		x /= t, y /= t;
		return *this;
	}

	Point operator-() const { return Point(-x, -y); }

	friend Point operator+(Point a, Point b) { return a += b; }
	friend Point operator-(Point a, Point b) { return a -= b; }

	// 标量乘除: 返回 Point<common_type_t<T, U>> (C++14), 自动算公共类型
	// <ll,ll>=ll / <ll,DB>=DB / <DB,ll>=DB; R==T 走 copy ctor, R!=T 走 converting ctor
	template<class U>
	friend auto operator*(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r *= b;
		return r;
	}

	template<class U>
	friend auto operator*(U a, Point b) {
		Point<common_type_t<T, U> > r = b;
		r *= a;
		return r;
	}

	template<class U>
	friend auto operator/(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r /= b;
		return r;
	}

	friend bool operator<(Point a, Point b) {
		int sx = sgn(a.x - b.x);
		if (sx != 0) return a.x < b.x;
		return a.y < b.y;
	}

	friend bool operator>(Point a, Point b) { return b < a; }

	friend bool operator==(Point a, Point b) {
		return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
	}

	friend bool operator!=(Point a, Point b) { return !(a == b); }

	friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
	friend ostream &operator<<(ostream &os, Point p) { return os << "(" << p.x << ", " << p.y << ")"; }

	auto norm() const {
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t)x * x + (__int128_t)y * y;
		} else {
			return x * x + y * y;
		}
	}

	DB abs() const { return sqrtL(norm()); }

	Point rot90() const {
		return Point(-y, x);
	}

	Point<DB> rot(DB ang) const {
		return Point<DB>(cosl(ang) * x - sinl(ang) * y, sinl(ang) * x + cosl(ang) * y);
	}

	// L1 范数 (曼哈顿) = |x| + |y|. 整型分支走 __int128_t 防溢出.
	auto normL1() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t)ax + (__int128_t)ay;
		} else {
			return ax + ay;
		}
	}

	// Linf 范数 (切比雪夫) = max(|x|, |y|). 返回类型与 T 同.
	T normLinf() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		return ax > ay ? ax : ay;
	}
};

template<class T, class U>
auto cross(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	//（改为这个非float，那么在类型为I128时，仍然可以计算）
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		return (__int128_t)a.x * b.y - (__int128_t)a.y * b.x;
	} else {
		return a.x * b.y - a.y * b.x;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) × (b - o)
// 用途: 判 3 点 turn (>0 左转, <0 右转, =0 共线) / 2 倍三角形有向面积 / 凸包面积扫描
template<class T, class U, class V>
auto cross(Point<T> o, Point<U> a, Point<V> b) {
	return cross(a - o, b - o);
}

template<class T, class U>
auto dot(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		return (__int128_t)a.x * b.x + (__int128_t)a.y * b.y;
	} else {
		return a.x * b.x + a.y * b.y;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) · (b - o)
// 用途: 判夹角钝/直/锐 (>0 锐, =0 直, <0 钝) / 投影长度的有符号 2 倍 / 点在线段上的位置判定
template<class T, class U, class V>
auto dot(Point<T> o, Point<U> a, Point<V> b) {
	return dot(a - o, b - o);
}

// 采用两点式
template<class T>
struct Line {
	Point<T> p1, p2;

	Line() = default;

	Line(Point<T> a, Point<T> b) : p1(a), p2(b) {
	}

	// Line<U> -> Line<T> 隐式 (common_type 单调升档方向, 同 Point converting ctor)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	Line(const Line<U> &o) : p1(o.p1), p2(o.p2) {
	}

	// AC https://qoj.ac/submission/2146870
	Line(T k, T c) : p1(Point<T>(0, c)), p2(Point<T>(1, k + c)) {
	}

	friend bool operator<(Line a, Line b) {
		if (a.p1 != b.p1) return a.p1 < b.p1;
		return a.p2 < b.p2;
	}

	friend bool operator==(Line a, Line b) {
		if (a.p1 != b.p1) return false;
		if (a.p2 != b.p2) return false;
		return true;
	}

	friend istream &operator>>(istream &is, Line &e) {
		T a, b, c, d;
		is >> a >> b >> c >> d;
		e = Line(Point<T>(a, b), Point<T>(c, d));
		return is;
	}

	friend ostream &operator<<(ostream &os, Line l) {
		return os << "<" << l.p1 << ", " << l.p2 << ">";
	}
};

Line<DB> gen_line_from_general(DB a, DB b, DB c) {
	// 方向向量 (b, -a)
	Point<DB> p1, p2;
	if (b != 0) {
		p1 = Point<DB>(0, -c / b);
	} else {
		p1 = Point<DB>(-c / a, 0);
	}
	p2 = Point<DB>(p1.x + b, p1.y - a);
	return Line<DB>(p1, p2);
}

// 使用这个东西，Point 必须是 double 等浮点类型
template<class T, class U>
Point<DB> project(Point<T> p, Line<U> l) {
	Point<DB> vec = l.p2 - l.p1;
	//                        这个距离反正早除晚除都要除掉
	DB r = dot(vec, p - l.p1) / ((DB)vec.x * vec.x + vec.y * vec.y);
	return l.p1 + vec * r;
}

template<class T, class U>
Point<DB> reflect(Point<T> p, Line<U> l) {
	Point<DB> proj = project(p, l);
	return proj + proj - p;
}

mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

constexpr int ON_SEGMENT = 0;
constexpr int COUNTER_CLOCKWISE = 1;
constexpr int CLOCKWISE = -1;
constexpr int ONLINE_BACK = 2;
constexpr int ONLINE_FRONT = -2;

template<class T, class U>
int CCW(Point<T> p, Line<U> l) {
	auto a = l.p2 - l.p1;
	auto b = p - l.p1;
	if (sgn(cross(a, b)) > 0) {
		return COUNTER_CLOCKWISE;
	}
	if (sgn(cross(a, b)) < 0) {
		return CLOCKWISE;
	}
	if (sgn(dot(a, b)) < 0) {
		return ONLINE_BACK;
	}
	if (a.norm() < b.norm()) return ONLINE_FRONT;
	return ON_SEGMENT;
}

template<class T, class U>
bool isOrthogonal(Line<T> a, Line<U> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(dot(c, d));
}

template<class T, class U>
bool isParallel(Line<T> a, Line<U> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(cross(c, d));
}

template<class T, class U>
bool isSegIntersect(Line<T> a, Line<U> b) {
	// 判断线段相交
	return CCW(b.p1, a) * CCW(b.p2, a) <= 0 && CCW(a.p1, b) * CCW(a.p2, b) <= 0;
}

// bool isIntersectStrict(Line a,Line b){    // 判断线段相交
//     return CCW(b.p1,a)*CCW(b.p2,a)<0 && CCW(a.p1,b)*CCW(a.p2,b)<0;
// }
// p+tv=q+sw
// (p-q) x w+tv x w = 0     (利用叉乘乘以自身为0，消掉sw)
// t=-(p-q)x w/(vxw)
// 传入的是方向式  拿到的是两直线交点
template<class T, class U>
Point<DB> getintersect(const Line<T> &a, const Line<U> &b) {
	Point<DB> p = a.p1, v = a.p2 - a.p1, q = b.p1, w = b.p2 - b.p1;
	Point<DB> u = p - q;
	DB t = (DB)cross(w, u) / cross(v, w);
	return p + v * t;
}

// 距离平方（不开方）：旋转卡壳里 ans 反复更新，留到最后一次 sqrt
template<class T, class U>
auto distancePPNorm(const Point<T> &a, const Point<U> &b) {
	return (a - b).norm();
}

// L2 欧几里得距离 (sqrt 版, 用 long double). 整型坐标走 isqrt + fraction 不丢精度.
template<class T, class U>
DB distancePP(const Point<T> &a, const Point<U> &b) {
	return (a - b).abs();
}

// L1 曼哈顿距离 = |dx| + |dy|. 返回类型继承 normL1 (整型 -> __int128_t, 浮点 -> T).
template<class T, class U>
auto distancePPL1(const Point<T> &a, const Point<U> &b) {
	return (a - b).normL1();
}

// Linf 切比雪夫距离 = max(|dx|, |dy|). 返回类型 T.
template<class T, class U>
T distancePPLinf(const Point<T> &a, const Point<U> &b) {
	return (a - b).normLinf();
}

// 也可以用 project 来算
template<class T, class U>
DB distancePL(Point<T> p, Line<U> l) {
	auto val = cross(l.p1, l.p2, p);
	return sgn(val) * val / (l.p2 - l.p1).abs();
}

// AC https://qoj.ac/submission/2001668
template<class T, class U>
DB distancePS(Point<T> p, Line<U> l) {
	// 避免 distanceSS 调用的时候发生这个退化（即线段退化为了点）
	if (l.p1 == l.p2) {
		return (p - l.p1).abs();
	}
	auto t = l.p2 - l.p1;
	if (sgn(dot(t, p - l.p1)) < 0) {
		return (p - l.p1).abs();
	}
	if (sgn(dot(t, p - l.p2)) > 0) {
		return (p - l.p2).abs();
	}
	return distancePL(p, l);
}

// AC https://qoj.ac/submission/2001588
template<class T, class U>
DB distanceSS(Line<T> a, Line<U> b) {
	if (isSegIntersect(a, b)) return 0;
	return min({distancePS(a.p1, b), distancePS(a.p2, b), distancePS(b.p1, a), distancePS(b.p2, a)});
}

// === polar_angle_sort 套件 (espanso :polarAngleSort, 拆自 :Point)
//     get_part_of_point + polar_angle_sort(Point) + polar_angle_sort(Line) + unique_line_polar_angle_sort
// 定义获取区域的辅助函数，辅助
template<class T>
int get_part_of_point(const Point<T> &p) {
	if (p.y < 0) return 0; // 下半平面 (-pi, 0)
	if (p.y == 0 && p.x >= 0) return 1; // 角度为 0 的部分 (含原点)
	return 2; // 上半平面 (0, pi]
}


struct PointColor {
	Point<ll> p;
	int c;
};

struct VecIJ {
	Point<ll> d;
	int i, j;

	bool operator<(const VecIJ &o) const {
		auto [parta,partb] = make_tuple(get_part_of_point(d), get_part_of_point(o.d));
		if (parta != partb) return parta < partb;
		return sgn(cross(d, o.d)) == 1;
	}
};


ll N;

void Solve() {
	cin >> N;
	vector<PointColor> A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i].p >> A[i].c;
	}
	vector<vector<ll> > dp(N, vector<ll>(N));
	for (int i = 0; i < N; ++i) {
		dp[i][i] = 1;
	}
	vector<VecIJ> vec_ijs;
	vec_ijs.reserve(N * N);
	for (int i = 0; i < SZ(A); ++i) {
		for (int j = 0; j < SZ(A); ++j) {
			if (i == j) continue;
			if (A[i].c != A[j].c) {
				auto diff = A[j].p - A[i].p;
				vec_ijs.push_back({diff, i, j});
			}
		}
	}
	sort(all(vec_ijs));
	for (auto [_,u,v]: vec_ijs) {
		for (int src = 0; src < N; ++src) {
			dp[src][v] += dp[src][u];
			dp[src][v] %= mod;
		}
	}
	ll ans = 0;
	for (int i = 0; i < N; ++i) {
		ans += dp[i][i];
		ans %= mod;
	}
	ans -= SZ(vec_ijs) / 2;
	ans -= N;
	ans %= mod;
	if (ans < 0) ans += mod;
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1233&rid=11368

*/

心路历程（WA，TLE，MLE……）

2026牛客暑期多校 7——Problem D. 天下第一武道会（要多手摸样例啊，然后猜测一些结论啊，想一想样例为什么做出这样的选择）（不想要卡死=尽量晚卡死啊 / 所谓的让区间最大，就是找到最大的右端点）

Posted on 2026-08-07 Edited on 2026-08-10

题目大意

这是一份为您整理好的整洁、规范的中文题面，去除了杂乱的内容且未包含任何解题思路：

题目描述：天下一武道会 (Tenkaichi Budōkai)

时间限制： C/C++/Rust/Pascal 1秒，其他语言2秒

空间限制： C/C++/Rust/Pascal 1024 MB，其他语言2048 MB

特殊判定 (Special Judge)： 是，64位整数输入输出格式：%lld

天下一武道会汇聚了来自世界各地的 $n$ 名武术家。武术家们的编号为 $1, 2, \ldots, n$ 。

在比赛开始前，两名官员分别提交了固定的优先级列表 $P$ 和 $Q$ 。每个列表都恰好包含每位武术家一次，尽管武术家在两个列表中的排列顺序可能不同。

初始时，列表为：

P = (p_1, p_2, \ldots, p_n)

Q = (q_1, q_2, \ldots, q_n)

其中这两个序列都是 $1, 2, \ldots, n$ 的排列。一旦提交，两个列表的顺序都不允许被重新排列。

比赛委员会使用以下规则来模拟比赛。只要至少还有两名武术家剩余，就可以进行一场比赛：

设 $u$ 和 $v$ 分别为当前列表 $P$ 和 $Q$ 中排在最前面的未被淘汰的武术家。

如果 $u = v$ ，说明两位官员提名了同一位武术家。由于武术家不能与自己对战，且任何一位官员都不能跳过他们列表中的第一位武术家，此时模拟过程将陷入停滞状态，无法继续进行后续比赛。
否则（即 $u \neq v$ ）， $u$ 和 $v$ 将进行对决。在模拟中，可以从 $\{u, v\}$ 中任意选择一名武术家 $z$ 作为败者。武术家 $z$ 将被淘汰出局，他也会同时从 $P$ 和 $Q$ 两个列表中被移除。移除后，每个列表中剩余武术家的相对顺序保持不变。

经过恰好 $n-1$ 场成功的比赛后，最终将只剩下一名武术家。这名武术家将被宣布为天下一武道会的冠军。

现在，你支持武术家 $x$ 。请判断：是否存在一种合法的比赛胜负序列，使得整个模拟过程永远不会陷入停滞状态，并且武术家 $x$ 最终成为冠军？

如果存在这样的序列，请输出任意一个符合条件的被淘汰武术家序列。

输入格式

第一行包含两个整数 $n$ 和 $x$ （ $2 \le n \le 2\times 10^5$ ， $1 \le x \le n$ ），分别表示武术家的数量和你希望成为冠军的武术家编号。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ 。保证序列 $P$ 是 $1, 2, \ldots, n$ 的一个排列。

第三行包含 $n$ 个整数 $q_1, q_2, \ldots, q_n$ 。保证序列 $Q$ 是 $1, 2, \ldots, n$ 的一个排列。

输出格式

如果在不陷入停滞状态的前提下，无法使武术家 $x$ 成为冠军，请输出一行 NO。

否则，第一行输出 YES。

第二行输出 $n-1$ 个整数 $z_1, z_2, \ldots, z_{n-1}$ ，其中 $z_i$ 表示在第 $i$ 场比赛中被淘汰的武术家。

注意：

在进行第 $i$ 场比赛前，设 $u_i$ 和 $v_i$ 分别为 $P$ 和 $Q$ 中剩余排在最前面的武术家。你的输出必须满足 $u_i \neq v_i$ 且 $z_i \in \{u_i, v_i\}$ 。在执行完全部的 $n-1$ 场淘汰操作后，剩余的唯一武术家必须是 $x$ 。

如果存在多个符合条件的淘汰序列，输出其中任意一个均视为正确。

样例

样例 1

输入：

Plaintext

1
2
3

3 3
2 3 1
3 1 2

输出：

Plaintext

NO

样例 2

输入：

Plaintext

1
2
3

3 1
2 1 3
3 2 1

输出：

Plaintext

1
2

YES
2 3

样例 3

输入：

Plaintext

1
2
3

5 1
2 4 3 1 5
4 3 5 2 1

输出：

Plaintext

1 2	YES 4 3 2 5

样例解释

下面是对 样例 3 输出的详细解释：

初始时， $P$ 和 $Q$ 中剩余排在最前面的武术家分别是 2 和 4。他们进行对决，武术家 4 被淘汰。列表更新为：

P = (2, 3, 1, 5)

Q = (3, 5, 2, 1)

下一场比赛在武术家 2 和 3 之间进行。武术家 3 被淘汰，列表更新为：

P = (2, 1, 5)

接下来，被提名的武术家是 2 和 5。武术家 2 被淘汰，此时：

P = (1, 5)

Q = (5, 1)

最后，武术家 1 和 5 面对面进行对决，武术家 5 被淘汰。两个列表现在都只剩下武术家 1。

因此，模拟过程从未陷入停滞，武术家 1 成功成为了天下一武道会的冠军。

思路讲解

不想要卡死=尽量晚卡死啊

那么维护这样子的一个距离啊，可以使用这个 pbds。


int choose_p_or_q() {
	if (aliveP.empty() || aliveQ.empty()) {
		return -1;
	}
	auto [pid,qid] = make_tuple(*aliveP.begin(), *aliveQ.begin());
	ll pval = P[pid];
	ll qval = Q[qid];
	if (pval == qval) {
		return -1;
	}
	ll disp = aliveQ.order_of_key(valToQPos[pval]);
	ll disq = aliveP.order_of_key(valToPPos[qval]);
	auto erase_q = [&]() {
		++ans_idx;
		Ans[ans_idx] = Q[qid];
		aliveQ.erase(qid);
		aliveP.erase(valToPPos[qval]);
	};
	auto erase_p = [&]() {
		++ans_idx;
		Ans[ans_idx] = P[pid];
		aliveP.erase(pid);
		aliveQ.erase(valToQPos[pval]);
	};
	if (pval == X) {
		erase_q();
	} else if (qval == X) {
		erase_p();
	} else if (disp >= disq) {
		erase_q();
	} else {
		erase_p();
	}
	return 0;
}

不断反复调用 choose_p_or_q()，即可啊。

while (SZ(aliveP) >= 2 || SZ(aliveQ) >= 2) {
	int res = choose_p_or_q();
	if (res == -1) {
		cout << "NO\n";
		return;
	}
}
cout << "YES\n";
for (int i = 1; i <= ans_idx; ++i) {
	cout << Ans[i] << " ";
}

AC代码

AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84410045

源代码

// teamname: Gospel_rock
/**
 * Problem: Tenkaichi Budōkai
 * Contest: 
 * Judge: NowCoder
 * URL: https://ac.nowcoder.com/acm/contest/133882/D
 * Created: 2026-08-08 01:42:06
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag,
	tree_order_statistics_node_update>;

ll N, X;
int P[MAXN], Q[MAXN], valToQPos[MAXN], valToPPos[MAXN];
ll ans_idx = 0;
ll Ans[MAXN];
ordered_set<ll> aliveP;
ordered_set<ll> aliveQ;


void init() {
	ans_idx = 0;
	aliveP.clear();
	aliveQ.clear();
}

int choose_p_or_q() {
	if (aliveP.empty() || aliveQ.empty()) {
#ifdef LOCAL
		cerr << "aliveP:" << SZ(aliveP) << " aliveQ:" << SZ(aliveQ) << "\n";
#endif
		return -1;
	}
	auto [pid,qid] = make_tuple(*aliveP.begin(), *aliveQ.begin());
	ll pval = P[pid];
	ll qval = Q[qid];
	if (pval == qval) {
		return -1;
	}
	ll disp = aliveQ.order_of_key(valToQPos[pval]);
	ll disq = aliveP.order_of_key(valToPPos[qval]);
	auto erase_q = [&]() {
		++ans_idx;
		Ans[ans_idx] = Q[qid];
		aliveQ.erase(qid);
		aliveP.erase(valToPPos[qval]);
	};
	auto erase_p = [&]() {
		++ans_idx;
		Ans[ans_idx] = P[pid];
		aliveP.erase(pid);
		aliveQ.erase(valToQPos[pval]);
	};
	if (pval == X) {
		erase_q();
	} else if (qval == X) {
		erase_p();
	} else if (disp >= disq) {
		erase_q();
	} else {
		erase_p();
	}
	return 0;
}

void Solve() {
	cin >> N >> X;
	init();
	for (int i = 1; i <= N; ++i) {
		cin >> P[i];
		valToPPos[P[i]] = i;
		aliveP.insert(i);
	}
	for (int i = 1; i <= N; ++i) {
		cin >> Q[i];
		valToQPos[Q[i]] = i;
		aliveQ.insert(i);
		// valToQPos.set(Q[i],i);
	}
	while (SZ(aliveP) >= 2 || SZ(aliveQ) >= 2) {
		int res = choose_p_or_q();
		if (res == -1) {
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
	for (int i = 1; i <= ans_idx; ++i) {
		cout << Ans[i] << " ";
	}
	cout << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase = 1; testcase <= lT; ++testcase)
	Solve();
	return 0;
}

/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84410045

*/