P4604 [WC2017] 挑战

### 洛谷不保证此类毒瘤题的评测结果准确性。 你和同学们找了三道题目用来练习。 这次练习的目标是写出能在时间限制里通过尽量大规模数据的代码。 同学们纷纷写出了优秀的代码。现在，他们向你发起了挑战，他们对每个问题都设置了若干个测试数据，这是他们能通过的最大规模的测试数据。现在，他们想看一看你写的代码究竟能超过多少同学的代码，通过多大规模的测试数据。 本题分为 $3$ 个任务，每个任务对应一道题和相应的若干个测试点，你需要对于每个任务，设计一个能通过尽量多测试点的程序。

## 任务一 给定 $n$ 个 $32$ 位无符号整数，将它们从小到大排序。 ## 任务二 有 $2n$ 个人在玩 「石头剪刀布」 游戏。他们排成两排，每排 $n$ 个人。每个人在每一局游戏都使用固定策略，即对于第 $i (i \in 1, 2)$ 排的第 $j (0 \leq j < n)$ 个人，用一个整数 $a_{ij}$ 表示他的策略，其中 $0$ 表示只出石头，$1$ 表示只出剪刀，$2$ 表示只出布。 现在有 $q$ 个询问，每个询问给定三个整数 $x,y,l(0\leq x,y

此题提供了模板程序。选手可以在此基础上编写自己的程序，模板程序详见下文数据范围与提示。 第一行一个整数$ task\_id(1\leq task\_id\leq3)$，表示任务编号。接下来是每个具体任务的输入内容。 在输入的同一行中，相邻的两个整数会被一个空格隔开。 对于任务一：一行，两个整数 $n,s$。令 $a_0=next\_integer(s),a_i=next\_integer(a_{i-1}),1\leq i

对于任务1：令 $b$ 为已经排好序的数组，调用 ```output_arr(b, n * 4)``` 即可。 对于任务2：将每个询问的答案依次存入 $32$ 位无符号整数数组 $b$ 中（即，存入 $b_0,b_1,⋯,b_{q-1}$ 中），然后调用 ```output_arr(b, q * 4)``` 即可。 对于任务3：输出一个整数，表示不同的方案数除以 $2^{32}$​​ 得到的余数。

## 数据范围与提示 | 任务编号 | 分值 | 测试点编号 | 数据范围与约定 | 时间限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | 5 | 1 | $n=100000$ | 3s | | 1 | 19 | 2 | $n=10^8$ | 4s | | 1 | 11 | 3 | $n=2\times10^8$ | 6s | | 2 | 7 | 4 | $n=q=1000$ | 3s | | 2 | 23 | 5 | $n=q=300000$ | 3s | | 3 | 9 | 6 | $n=1000$ | 3s | | 3 | 5 | 7 | $n=120000$ | 3s | | 3 | 7 | 8 | $n=225000$ | 3s | | 3 | 14 | 9 | $n=266666$ | 3s | ## 模板程序 ### C++模板 ``` #include #include #include typedef unsigned int u32; typedef unsigned long long u64; inline u32 next_integer(u32 x) { x ^= x > 17; x ^= x 17; x ^= x 17; x ^= x 17; x ^= x 17); x := x xor (x 17); x := x xor (x