P4604 [WC2017] Challenge

### Luogu does not guarantee the accuracy of judging results for this kind of extremely tricky problem. You and your classmates found three problems to practice. The goal of this practice is to write code that can pass testdata of as large a size as possible within the time limit. Your classmates have written excellent code. Now, they challenge you: for each problem, they have prepared several test cases, representing the largest-scale testdata that their own code can pass. Now, they want to see how many classmates’ code your program can outperform, and how large-scale testdata it can pass. This problem is divided into $3$ tasks. Each task corresponds to one problem and its related test points. For each task, you need to design a program that can pass as many test points as possible.

## Task 1 Given $n$ $32$-bit unsigned integers, sort them in non-decreasing order. ## Task 2 There are $2n$ people playing Rock-Paper-Scissors. They stand in two rows, with $n$ people in each row. Each person uses a fixed strategy in every round. Specifically, for the $j$-th person $(0 \leq j < n)$ in row $i$ $(i \in 1, 2)$, use an integer $a_{ij}$ to represent their strategy, where $0$ means always play Rock, $1$ means always play Scissors, and $2$ means always play Paper. Now there are $q$ queries. Each query gives three integers $x, y, l(0\leq x,y

This problem provides template code. Contestants may write their program based on it. The template code is shown below in the Constraints and Hint section. The first line contains one integer $task\_id(1\leq task\_id\leq3)$, indicating the task number. The following input depends on the specific task. In the same input line, any two adjacent integers are separated by a single space. For Task 1: one line with two integers $n, s$. Let $a_0=next\_integer(s),a_i=next\_integer(a_{i-1}),1\leq i

For Task 1: let $b$ be the sorted array, and call ```output_arr(b, n * 4)```. For Task 2: store the answer of each query in order into a $32$-bit unsigned integer array $b$ (i.e., into $b_0,b_1,\cdots,b_{q-1}$), then call ```output_arr(b, q * 4)```. For Task 3: output one integer, which is the remainder of the number of different ways modulo $2^{32}$.

## Constraints and Hint | Task ID | Score | Test Point ID | Constraints and Notes | Time Limit | | :----------: | :----------: | :----------: | :----------: | :----------: | | 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 | ## Template Code ### C++ Template ``` #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