Background

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.

Problem Description

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<n,1\leq l\leq n-max(x,y))$, asking: after the people from $x \sim x+l-1$ in the first row play against the people from $y \sim y+l-1$ in the second row, how many people in the first row will win.

Here, “play against” means: for all integers $i$ such that $0 \leq i < l$, let the person at position $x+i$ in the first row play Rock-Paper-Scissors against the person at position $y+i$ in the second row.

Task 3

We call a bracket sequence valid if it consists only of left and right parentheses, the numbers of the two types are equal, and in any prefix the number of left parentheses is not less than the number of right parentheses. Now you are given a string consisting of (, ) and ?. How many different ways are there to replace each ? with a parenthesis so that the string becomes a valid bracket sequence. Two ways are different if and only if there is at least one position where ? is replaced by different parentheses.

Input Format

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<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 contains a string of length $n$ consisting only of $0, 1, 2$. The integer represented by the $i$-th character is the strategy of the $i$-th person in the first row (i.e., $a_{1i}$). The third line has the same format as the second line, representing the strategies of the people in the second row.

For Task 3: the first line contains one integer $n$, the length of the given string. The second line contains one string, which is the given string.

Output Format

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}$.

1
100000 2017012501

4275990336

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

3349208141

3
4
(???

2

3
4
)???

0

Hint

Constraints and Hint

Template Code

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

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();
var
    n : longint;
    s : ansistring;
    ans : u32;
begin
    read(n);
    read(s);

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

    writeln(ans);
end;


var
    task_id : longint;

begin
    read(task_id);

    if task_id = 1 then begin
        Sorting_main();
    end else if task_id = 2 then begin
        Game_main();
    end else if task_id = 3 then begin
        Parentheses_main();
    end;
    close(input); close(output);
end.

Translated by ChatGPT 5