P9754 [CSP-S 2023] Struct

In high-level languages such as C++, besides basic types like `int` and `float`, you can usually define your own struct types. In this problem, you need to simulate a struct definition method similar to that of a C++-like high-level language, and compute the corresponding memory usage and related information.

In this language, there are $4$ basic types: `byte`, `short`, `int`, `long`, which occupy $1$, $2$, $4$, $8$ bytes of memory, respectively. When defining a struct **type**, you need to provide the **type name** and its **members**. Each member must be given, in order, with its **type** and **name**. A type can be a basic type or a struct type that has been **defined earlier**. Note that defining a struct **type** does not define any concrete variable, so it does not occupy memory. When defining an **object** (an instance/variable), you need to provide the object’s **type** and **name**. Objects occupy memory according to the following rules: - All members inside an object are laid out in memory in the **same order as in the definition**. The same applies to members whose type is a struct. - To ensure efficient memory access, the object’s address allocation must satisfy the **alignment rules**: for any type, both the **size** of the type and the **starting address** of an object of that type in memory must be aligned to an **integer multiple** of the type’s alignment requirement. Specifically: - For basic types: the alignment requirement equals the size it occupies. For example, `int` must be aligned to $4$ bytes, and similarly for the others. - For struct types: the alignment requirement equals the **maximum** alignment requirement among its members. For example, a struct type containing `int` and `short` must be aligned to $4$ bytes. Here is an example (written in C++ format): ```cpp struct d { short a; int b; short c; }; d e; ``` This code defines the struct type `d` and an object `e`. Object `e` contains three members `e.a`, `e.b`, `e.c`, occupying address ranges $0 \sim 1$, $4 \sim 7$, and $8 \sim 9$, respectively. Since type `d` needs to be aligned to $4$ bytes, `e` occupies addresses $0 \sim 11$, with a total size of $12$ bytes. You need to process $n$ operations. Each operation is one of the following four types: 1. Define a struct type. Specifically, you are given a positive integer $k$ and strings $s, t_1, n_1, \dots, t_k, n_k$, where $k$ is the number of members, $s$ is the type name, $t_1, t_2, \dots, t_k$ are the member types in order, and $n_1, n_2, \dots, n_k$ are the member names in order. You need to output the size and alignment requirement of this struct type, separated by a space. 2. Define an object. Specifically, you are given strings $t, n$, representing the object’s type and name. All defined objects are placed in order in memory starting from address $0$, and must satisfy the address alignment rules. You need to output the starting address of the newly defined object. 3. Access an object. Specifically, you are given a string $s$ representing the object to be accessed. As in C++ and similar languages, `.` is used to access members of a struct type. For example, `a.b.c` means `a` is a defined object; it is a struct type and has a member named `b`, which is also a struct type and has a member named `c`. You need to output the starting address of the **innermost** element accessed as above. 4. Access a memory address. Specifically, you are given a non-negative integer $addr$, representing the address to access. You need to determine whether there exists a **basic-type** element that occupies this address. If yes, output that element in the same access format as in operation 3; otherwise output `ERR`.

Line $1$: a positive integer $n$, the number of operations. The following lines describe the operations in order. The first integer on each line is $op$, the operation type: - If $op = 1$, first input a string $s$ and a positive integer $k$, representing the type name and number of members. Then follow $k$ lines, each containing two strings $t_i, n_i$, representing the type and name of each member in order. - If $op = 2$, input two strings $t, n$, representing the type and name of the object. - If $op = 3$, input one string $s$, representing the object to be accessed. - If $op = 4$, input one non-negative integer $addr$, representing the address to be accessed.

Output $n$ lines, in order, each being the result of the corresponding operation, as required in the statement.

#### Sample 1 Explanation In struct type `a`, the `short` member `aa` occupies addresses $0 \sim 1$, and the `int` member `ab` occupies addresses $4 \sim 7$. Since its alignment requirement is $4$ bytes, its size is $8$ bytes. Similarly, the size of struct type `b` is $16$ bytes, and its alignment requirement is $8$ bytes. #### Sample 2 See `struct/struct2.in` and `struct/struct2.ans` in the contestant directory. #### Sample 2 Explanation In the second operation 4, the accessed memory address lies exactly in a “hole” left for address alignment, so no basic-type element occupies it. #### Sample 3 See `struct/struct3.in` and `struct/struct3.ans` in the contestant directory. #### Constraints For all data, $1 \le n \le 100$, $1 \le k \le 100$, $0 \le addr \le 10^{18}$. All defined struct type names, member names, and object names consist of at most $10$ lowercase letters, and none of them is `byte,short,int,long` (i.e., they do not share a name with any basic type). All defined struct type names and object names are pairwise distinct, and member names within the same struct are pairwise distinct. However, different structs may have the same member name, and a member name within some struct may also be the same as a defined struct or object name. It is guaranteed that all operations follow the rules and requirements described in the statement. In particular, struct definitions will not include nonexistent types, and accesses will not refer to nonexistent objects or members. It is guaranteed that the size of any struct and the maximum memory address occupied by defined objects do not exceed $10^{18}$. | Test Point | Special Property | | :----------: | :----------: | | $1$ | A, D | | $2\sim 3$ | A | | $4\sim 5$ | B, D | | $6\sim 8$ | B | | $9\sim 10$ | C, D | | $11\sim 13$ | C | | $14\sim 16$ | D | | $17\sim 20$ | None | Special property A: there is no operation $1$. Special property B: there is only one operation $1$. Special property C: in all operations $1$, all member types are basic types. Special property D: the only basic type is `long`. #### Hint The formal definitions of the alignment requirement and size of a struct type are as follows: - Suppose the struct has $k$ members, with sizes $s_1,...,s_k$ and alignment requirements $a_1,...,a_k$. - Then the alignment requirement of this struct is $a=\max\{a_1,...,a_k\}$. - Let the **address offsets** of these members in the layout be $o_1,...,o_k$. Then: - $o_1 = 0$. - For $i=2,...,k$, $o_i$ is the smallest value such that $o_{i-1}+s_{i-1}\le o_i$ and $a_i$ divides $o_i$. - The size $s$ of this struct is the smallest value such that $o_k+s_k\le s$ and $a$ divides $s$. The formal definition of the memory layout when defining objects is as follows: - Suppose the $i$-th defined object has size $s_i$, alignment requirement $a_i$, and starting address $b_i$. - Then $b_1 = 0$. For $2\le i$, $b_i$ is the smallest value such that $b_{i-1} + s_{i-1}\le b_i$ and $a_i$ divides $b_i$. Translated by ChatGPT 5