CF2025F.Choose Your Queries

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个包含 $n$ 个整数的数组 $a$ （编号从 $1$ 到 $n$ ），初始时所有元素均为零。

你需要处理 $q$ 个操作，第 $i$ 个操作包含两个不同的整数 $x_i$ 和 $y_i$ 。在第 $i$ 个操作中，你需要选择一个整数 $p$ （ $p$ 可以是 $x_i$ 或 $y_i$ ），以及一个整数 $d$ （ $d$ 可以是 $1$ 或 $-1$ ），并执行 $a_p = a_p + d$ 。

每次操作后，数组 $a$ 的所有元素都必须是非负整数。

请你以使得最后一次操作后 $a$ 所有元素之和尽可能小的方式，依次处理所有操作。

输入格式

第一行包含两个整数 $n$ 和 $q$ （ $2 \le n \le 3 \cdot 10^5$ ， $1 \le q \le 3 \cdot 10^5$ ），分别表示数组 $a$ 的长度和操作次数。

接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$ （ $1 \le x_i, y_i \le n$ ， $x_i \ne y_i$ ），表示第 $i$ 个操作的描述。

输出格式

对于每个操作，输出一行，包含两个字符：

第一个字符为 x，表示选择 $p = x_i$ ；为 y，表示选择 $p = y_i$ ；
第二个字符为 +，表示选择 $d = 1$ ；为 -，表示选择 $d = -1$ 。

如果有多种方案，输出任意一种均可。

输入输出样例

输入#1
```
3 4
1 2
3 2
3 1
1 2
```
输出#1
```
y+
x+
x-
y-
```
输入#2
```
4 4
1 2
2 3
3 4
3 2
```
输出#2
```
y+
y+
x-
y-
```
输入#3
```
4 2
2 1
4 3
```
输出#3
```
y+
x+
```

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页