Problem Background

Abuse of this problem for judging purposes will result in account suspension. Luogu does not guarantee the accuracy of the judging results for such problematic problems.

You and your classmates have found three problems for practice.

The goal of this practice is to write code that can handle the largest possible datasets within the time limits.

Your classmates have written excellent codes. Now, they challenge you by setting up several test cases for each problem, which are the largest datasets they can handle. They want to see how many of their codes your code can surpass and how large a dataset it can handle.

This problem is divided into 3 tasks, each corresponding to a problem and several test points. You need to design a program for each task that can handle as many test points as possible.

Problem Description

Task 1

Given \( n \) 32-bit unsigned integers, sort them in ascending order.

Task 2

There are \( 2n \) people playing "Rock-Paper-Scissors" game. They are arranged in two rows, each containing \( n \) people. Each person uses a fixed strategy in every game, represented by an integer \( a_{ij} \) where \( 0 \) means only rock, \( 1 \) means only scissors, and \( 2 \) means only paper.

There are \( q \) queries, each giving three integers \( x, y, l (0 \leq x, y < n, 1 \leq l \leq n - \max(x, y)) \), asking how many people in the first row will win after the first row's \( x \sim x+l-1 \) individuals compete against the second row's \( y \sim y+l-1 \) individuals.

The term "compete" means for all integers \( i \) satisfying \( 0 \leq i < l \), the \( x+i \)-th person in the first row plays against the \( y+i \)-th person in the second row in "Rock-Paper-Scissors".

Task 3

A valid parenthesis string is defined as a string consisting only of left and right parentheses, with equal numbers of both, and no prefix having more right parentheses than left. Given a string consisting of (, ), and ?, find the number of different ways to replace each ? with a parenthesis such that the string becomes a valid parenthesis string. Two solutions are considered different if at least one position's ? is replaced with a different parenthesis.

Input Format

This problem provides a template program. Contestants can write their programs based on this template, which is detailed in the Data Range and Hints section below.

The first line contains an integer \( task\_id (1 \leq task\_id \leq 3) \), indicating the task number. The following lines contain the input for each specific task.

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 < n \), then \( a_0, a_1, \ldots, a_{n-1} \) are the \( n \) integers to be sorted.

For Task 2: The first line contains two integers \( n, q \). The second line is a string of length \( n \) containing only \( 0, 1, 2 \), representing the strategies of the first row. The third line is similar, representing the second row's strategies.

For Task 3: The first line contains an integer \( n \), the length of the given string. The second line is the given string.

Output Format

For Task 1: Let \( b \) be the sorted array, call output_arr(b, n * 4).

For Task 2: Store each query's answer in a 32-bit unsigned integer array \( b \) (i.e., \( b_0, b_1, \ldots, b_{q-1} \)), then call output_arr(b, q * 4).

For Task 3: Output an integer, the number of different ways modulo \( 2^{32} \).

Sample Input and Output

Input Sample #1

1
100000 2017012501

Output Sample #1

4275990336

Input Sample #2

2
6 6
200100
200211
5 3 1
2 0 1
2 0 3
2 0 2
2 3 4
0 1 3

Output Sample #2

3349208141

Input Sample #3

3
4
(???

Output Sample #3

2

Input Sample #4

3
4
)???

Output Sample #4

0

Notes/Hints

Template Program

C++ Template

#include <stdio.h>
#include <string.h>
#include <algorithm>

typedef unsigned int u32;
typedef unsigned long long u64;

inline u32 next_integer(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

bool output_arr(void *a, u32 size) {
    if (size % 4) {
        return puts("-1"), 0;
    }

    u32 blocks = size / 4;
    u32 *A = (u32 *)a;
    u32 ret = size;
    u32 x = 23333333;
    for (u32 i = 0; i < blocks; i++) {
        ret = ret ^ (A[i] + x);
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
    }

    return printf("%u\n", ret), 1;
}

// ===== header ======

namespace Sorting {
void init_data(u32 *a, int n, u32 seed) {
    for (int i = 0; i < n; i++) {
        seed = next_integer(seed);
        a[i] = seed;
    }
}

void main() {
    int n;
    u32 seed;
    scanf("%d%u", &n, &seed);

    u32 *a = new u32[n];
    init_data(a, n, seed);

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
}
}

namespace Game {
void main() {
    int n, q;
    scanf("%d%d", &n, &q);

    char *s1 = new char[n + 1];
    char *s2 = new char[n + 1];
    scanf("%s%s", s1, s2);

    u32 *anss = new u32[q];
    int *q_x = new int[q];
    int *q_y = new int[q];
    int *q_len = new int[q];

    for (int i = 0; i < q; i++) {
        scanf("%d%d%d", q_x + i, q_y + i, q_len + i);
    }

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
}
}

namespace Parentheses {
void main() {
    int n;
    scanf("%d", &n);

    char *s = new char[n + 1];
    scanf("%s", s);

    u32 ans;
    // ans = solve(n, s);

    printf("%u\n", ans);
}
}

int main() {
    int task_id;
    scanf("%d", &task_id);

    switch (task_id) {
        case 1:
            Sorting::main();
            break;
        case 2:
            Game::main();
            break;
        case 3:
            Parentheses::main();
            break;
    }

    return 0;
}

C Template

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define bool int
#define true 1
#define false 0

typedef unsigned int u32;
typedef unsigned long long u64;

inline u32 next_integer(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

bool output_arr(void *a, u32 size) {
    if (size % 4) {
        return puts("-1"), 0;
    }

    u32 blocks = size / 4;
    u32 *A = (u32 *)a;
    u32 ret = size;
    u32 x = 23333333;
    u32 i;
    for (i = 0; i < blocks; i++) {
        ret = ret ^ (A[i] + x);
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
    }

    return printf("%u\n", ret), 1;
}

// ===== header ======

void Sorting_main() {
    int n;
    u32 seed;
    scanf("%d%u", &n, &seed);

    u32 *a = malloc(n * sizeof(u32));
    int i;
    for (i = 0; i < n; i++) {
        seed = next_integer(seed);
        a[i] = seed;
    }

    // sort(a, n);

    output_arr(a, n * sizeof(u32));
}

void Game_main() {
    int n, q;
    scanf("%d%d", &n, &q);

    char *s1 = malloc((n + 1) * sizeof(char));
    char *s2 = malloc((n + 1) * sizeof(char));
    scanf("%s%s", s1, s2);

    u32 *anss = malloc(q * sizeof(u32));
    int *q_x = malloc(q * sizeof(int));
    int *q_y = malloc(q * sizeof(int));
    int *q_len = malloc(q * sizeof(int));

    int i;

    for (i = 0; i < q; i++) {
        scanf("%d%d%d", q_x + i, q_y + i, q_len + i);
    }

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(anss, q * sizeof(u32));
}

void Parentheses_main() {
    int n;
    scanf("%d", &n);

    char *s = malloc((n + 1) * sizeof(char));
    scanf("%s", s);

    u32 ans;
    // ans = solve(n, s);

    printf("%u\n", ans);
}

int main() {
    int task_id;
    scanf("%d", &task_id);

    switch (task_id) {
        case 1:
            Sorting_main();
            break;
        case 2:
            Game_main();
            break;
        case 3:
            Parentheses_main();
            break;
    }

    return 0;
}

Pascal Template

```pascal
type
u32 = dword;
u64 = qword;
u32_p = ^u32;
u64_p = ^u64;
longint_p = ^longint;

function next_integer(x : u32) : u32; inline;
begin
x := x xor (x << 13);
x := x xor (x >> 17);
x := x xor (x << 5);
exit(x);
end;

function output_arr(a_in : pointer; size : u32) : boolean;
var
blocks : u32;
a, a_ed : u32_p;
ret, x : u32;
begin
if size mod 4 <> 0 then begin
writeln(-1);
exit(false);
end;

blocks := size div 4;
ret := size;
a := a_in;
a_ed := a + blocks;
x := 23333333;

while a < a_ed do begin
    ret := ret xor (a[0] + x);
    x := x xor (x << 13);
    x := x xor (x >> 17);
    x := x xor (x << 5);
    inc(a);
end;

writeln(ret);
exit(true);

end;

// ====== header ======

procedure init_data(a : u32_p; n : longint; seed : u32);
var
a_ed : u32_p;
begin
a_ed := a + n;
while a < a_ed do begin
seed := next_integer(seed);
a[0] := seed;
inc(a);
end;
end;

procedure Sorting_main();
var
n : longint;
seed : u32;
a : u32_p;
i : u32;
begin
read(n, seed);

a := Getmem(n * sizeof(u32));
init_data(a, n, seed);

// sort(a, n);

output_arr(a, n * sizeof(u32));

end;

procedure Game_main();
var
n, q : longint;
s1, s2 : ansistring;
anss : u32_p;
q_x, q_y, q_len : longint_p;
i : longint;
begin
readln(n, q);
readln(s1);
readln(s2);

anss := Getmem(q * sizeof(u32));
q_x := Getmem(q * sizeof(longint));
q_y := Getmem(q * sizeof(longint));
q_len := Getmem(q * sizeof(longint));

for i := 0 to q - 1 do begin
    read(q_x[i], q_y[i], q_len[i]);
end;

// solve(n, q, s1, s2, q_x, q_y, q_len, anss);

output_arr(anss, q * sizeof(u32));

end;

procedure Parentheses_main();

见题面 Input 部分

见题面 Output 部分