Luogu P9754 [CSP-S 2023] Struct Solution

Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

Problem Link
Luogu Blog Blog Garden

Basic Approach

This problem tests coding implementation skills. The core ideas are:

Recursive element creation allows up to $100^{100}$ distinct base-type elements. Even considering address limits, elements can reach $10^{18}$. Iteratively constructing each element is infeasible in time and space.
However, queries are limited. Only a small subset of elements are accessed during queries. Thus, maintain a list of top-level elements (not nested within others) and traverse hierarchically based on query addresses/names. Specific handling for four operations:
- For $op=1$: Store type info, compute size and alignment requirements, then output.
- For $op=2$: Track the first allocatable address. Align, compute, then output.
- For $op=3$: Start from top-level, traverse layers to compute address.
- For $op=4$: Start from top-level, compare current address ranges with target, then output element name.

Based on this, three storage approaches emerge:

Type names as identifiers: Intuitive but inefficient, discarded.
Map type names to indices: More efficient but cumbersome, discarded.
Store types as structs with pointers: Efficient and intuitive. Adopted.

Step-by-Step Explanation

Preparation

Define LL as long long, setmax(x, y) as x = max(x, y):

1
2
3
4
5
6


inline void setmax(int& x, int y)
{
    if(x < y) x = y;
}

using LL = long long;

Data Type Storage

Define struct DataType:

1
2
3
4
5
6
7


struct DataType
{
    const string name; // Type name
    LL size, actual_size; // Aligned size and actual data length
    int indent; // Alignment requirement
    vector<pair<DataType*, string>> members; // Members stored as <type pointer, name>
};

$$ {aligned\_addr} = \lceil \frac {addr} {indent} \rceil \times indent $$

1
2
3
4


inline LL shift(LL addr)
{
    return addr % indent? (addr / indent + 1) * indent: addr;
}

Maintenance after type definition:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


inline void maintain()
{
    size = indent = 0;
    for(const auto& m: members)
    {
        setmax(indent, m.first->indent);
        size = m.first->shift(size) + m.first->size;
    }
    actual_size = size;
    size = shift(size);
}

Store types via unordered_map:

1

unordered_map<string, DataType*> types;

Add base types:

1
2
3
4
5
6
7
8
9


auto add_base_type = [&](string name, int size) -> void {
    DataType* t = new DataType(name);
    t->size = t->indent = t->actual_size = size;
    types[name] = t;
};
add_base_type("byte", 1);
add_base_type("short", 2);
add_base_type("int", 4);
add_base_type("long", 8);

Operation 1: Define Type

Process input and compute alignment:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


string s;
int k;
cin >> s >> k;
DataType* type = new DataType(s);
types[s] = type;
type->members.resize(k);
for(auto& m: type->members)
{
    string t;
    cin >> t >> m.second;
    m.first = types[t];
}
type->maintain();
cout << type->size << ' ' << type->indent << '\n';

Operation 2: Define Element

Track current address and top-level elements:

1
2


LL cur_addr = 0LL;
vector<Object> toplevel_objects;

Object definition:

1
2
3
4
5
6


struct Object
{
    DataType* type; // Element type
    string name;    // Element name
    LL addr;        // Start address
};

Compute and save element:

1
2
3
4
5
6
7
8


Object obj;
string t;
cin >> t >> obj.name;
obj.type = types[t];
obj.addr = obj.type->shift(cur_addr);
cur_addr = obj.addr + obj.type->size;
toplevel_objects.push_back(obj);
cout << obj.addr << '\n';

Operation 3: Access Element

Split path and traverse layers:

1
2
3
4
5
6
7
8
9


inline void split(const string& s, char sep, vector<string>& res)
{
    string t;
    for(char c: s)
        if(c == sep)
            res.push_back(t), t.clear();
        else t += c;
    res.push_back(t);
}

Locate top-level element:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


string s;
cin >> s;
vector<string> ord;
split(s, '.', ord);
LL addr;
DataType* type;
for(auto& obj: toplevel_objects)
    if(obj.name == ord[0])
    {
        addr = obj.addr;
        type = obj.type;
        break;
    }

Traverse members:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


ord.erase(ord.begin());
for(string& s: ord)
    for(auto& m: type->members)
    {
        addr = m.first->shift(addr);
        if(m.second == s)
        {
            type = m.first;
            break;
        }
        addr += m.first->size;
    }
cout << addr << '\n';

Operation 4: Access Address

Locate containing top-level element:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


LL addr;
cin >> addr;
if(addr >= cur_addr)
{
    cout << "ERR\n";
    continue;
}
DataType* type = nullptr;
LL f_addr = 0LL;
string res;
for(auto& obj: toplevel_objects)
{
    if(addr < obj.addr) goto bad;
    if(addr < obj.addr + obj.type->size)
    {
        type = obj.type;
        res = obj.name;
        f_addr = obj.addr;
        break;
    }
}

Traverse nested members:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


while(addr < f_addr + type->actual_size && !type->members.empty())
    for(auto& m: type->members)
    {
        f_addr = m.first->shift(f_addr);
        if(addr < f_addr) goto bad;
        if(addr < f_addr + m.first->size)
        {
            type = m.first;
            res.push_back('.');
            res += m.second;
            break;
        }
        f_addr += m.first->size;
    }
if(addr < f_addr + type->actual_size) cout << res << '\n';
else cout << "ERR\n";
continue;
bad: cout << "ERR\n";

Full Code

Contest code (as explained):

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180


#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

inline void setmax(int& x, int y)
{
    if(x < y) x = y;
}

using LL = long long;

struct DataType
{
    const string name;
    LL size, actual_size;
    int indent;
    vector<pair<DataType*, string>> members;
    inline DataType(const string& n): name(n) {}
    inline LL shift(LL addr)
    {
        return addr % indent? (addr / indent + 1) * indent: addr;
    }
    inline void maintain()
    {
        size = indent = 0;
        for(const auto& m: members)
        {
            setmax(indent, m.first->indent);
            size = m.first->shift(size) + m.first->size;
        }
        actual_size = size;
        size = shift(size);
    }
};

struct Object
{
    DataType* type;
    string name;
    LL addr;
};

inline void split(const string& s, char sep, vector<string>& res)
{
    string t;
    for(char c: s)
        if(c == sep)
            res.push_back(t), t.clear();
        else t += c;
    res.push_back(t);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    unordered_map<string, DataType*> types;
    auto add_base_type = [&](string name, int size) -> void {
        DataType* t = new DataType(name);
        t->size = t->indent = t->actual_size = size;
        types[name] = t;
    };
    add_base_type("byte", 1);
    add_base_type("short", 2);
    add_base_type("int", 4);
    add_base_type("long", 8);
    int q;
    cin >> q;
    vector<Object> toplevel_objects;
    LL cur_addr = 0LL;
    while(q--)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            string s;
            int k;
            cin >> s >> k;
            DataType* type = new DataType(s);
            types[s] = type;
            type->members.resize(k);
            for(auto& m: type->members)
            {
                string t;
                cin >> t >> m.second;
                m.first = types[t];
            }
            type->maintain();
            cout << type->size << ' ' << type->indent << '\n';
        }
        else if(op == 2)
        {
            Object obj;
            string t;
            cin >> t >> obj.name;
            obj.type = types[t];
            obj.addr = obj.type->shift(cur_addr);
            cur_addr = obj.addr + obj.type->size;
            toplevel_objects.push_back(obj);
            cout << obj.addr << '\n';
        }
        else if(op == 3)
        {
            string s;
            cin >> s;
            vector<string> ord;
            split(s, '.', ord);
            LL addr;
            DataType* type;
            for(auto& obj: toplevel_objects)
                if(obj.name == ord[0])
                {
                    addr = obj.addr;
                    type = obj.type;
                    break;
                }
            ord.erase(ord.begin());
            for(string& s: ord)
                for(auto& m: type->members)
                {
                    addr = m.first->shift(addr);
                    if(m.second == s)
                    {
                        type = m.first;
                        break;
                    }
                    addr += m.first->size;
                }
            cout << addr << '\n';
        }
        else // op == 4
        {
            LL addr;
            cin >> addr;
            if(addr >= cur_addr)
            {
                cout << "ERR\n";
                continue;
            }
            DataType* type = nullptr;
            LL f_addr = 0LL;
            string res;
            for(auto& obj: toplevel_objects)
            {
                if(addr < obj.addr) goto bad;
                if(addr < obj.addr + obj.type->size)
                {
                    type = obj.type;
                    res = obj.name;
                    f_addr = obj.addr;
                    break;
                }
            }
            while(addr < f_addr + type->actual_size && !type->members.empty())
                for(auto& m: type->members)
                {
                    f_addr = m.first->shift(f_addr);
                    if(addr < f_addr) goto bad;
                    if(addr < f_addr + m.first->size)
                    {
                        type = m.first;
                        res.push_back('.');
                        res += m.second;
                        break;
                    }
                    f_addr += m.first->size;
                }
            if(addr < f_addr + type->actual_size) cout << res << '\n';
            else cout << "ERR\n";
            continue;
            bad: cout << "ERR\n";
        }
    }
    for(auto it=types.begin(); it!=types.end(); it++)
        delete it->second;
    return 0;
}

Total: 180 lines (4.64KB), runtime 73ms.

Optimized version:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146


#include <bits/stdc++.h>
using namespace std;

using LL = long long;

struct DataType {
    const string name;
    LL size, actual_size;
    int indent;
    vector<pair<DataType*, string>> members;
    inline DataType(const string& n): name(n) {}
    inline LL shift(LL addr) {
        return addr % indent? (addr / indent + 1) * indent: addr;
    }
    inline void maintain() {
        size = indent = 0;
        for(const auto& m: members)
        {
            indent = max(indent, m.first->indent);
            size = m.first->shift(size) + m.first->size;
        }
        actual_size = size;
        size = shift(size);
    }
};

inline void split(const string& s, char sep, vector<string>& res) {
    string t;
    for(char c: s)
        if(c == sep) res.push_back(t), t.clear();
        else t += c;
    res.push_back(t);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    unordered_map<string, DataType*> types;
    auto add_base_type = [&](string name, int size) -> void {
        DataType* t = new DataType(name);
        t->size = t->indent = t->actual_size = size;
        types[name] = t;
    };
    add_base_type("byte", 1);
    add_base_type("short", 2);
    add_base_type("int", 4);
    add_base_type("long", 8);
    int q;
    cin >> q;
    vector<pair<DataType*, string>> toplevel_objects;
    LL cur_addr = 0LL;
    while(q--) {
        int op;
        cin >> op;
        if(op == 1) {
            string s;
            int k;
            cin >> s >> k;
            DataType* type = new DataType(s);
            types[s] = type;
            type->members.resize(k);
            for(auto& m: type->members) {
                string t;
                cin >> t >> m.second;
                m.first = types[t];
            }
            type->maintain();
            cout << type->size << ' ' << type->indent << '\n';
        }
        else if(op == 2) {
            string t, name;
            cin >> t >> name;
            DataType* type = types[t];
            cur_addr = type->shift(cur_addr);
            cout << cur_addr << '\n';
            cur_addr += type->size;
            toplevel_objects.emplace_back(type, name);
        }
        else if(op == 3) {
            string s;
            cin >> s;
            vector<string> ord;
            split(s, '.', ord);
            LL addr = 0LL;
            DataType* type;
            for(auto& obj: toplevel_objects) {
                addr = obj.first->shift(addr);
                if(obj.second == ord[0]) {
                    type = obj.first;
                    break;
                }
                addr += obj.first->size;
            }
            ord.erase(ord.begin());
            for(string& s: ord)
                for(auto& m: type->members) {
                    addr = m.first->shift(addr);
                    if(m.second == s) {
                        type = m.first;
                        break;
                    }
                    addr += m.first->size;
                }
            cout << addr << '\n';
        }
        else {
            LL addr;
            cin >> addr;
            if(addr >= cur_addr) {
                cout << "ERR\n";
                continue;
            }
            DataType* type = nullptr;
            LL f_addr = 0LL;
            string res;
            for(auto& obj: toplevel_objects) {
                f_addr = obj.first->shift(f_addr);
                if(addr < f_addr) goto bad;
                if(addr < f_addr + obj.first->size) {
                    type = obj.first;
                    res = obj.second;
                    break;
                }
                f_addr += obj.first->size;
            }
            while(addr < f_addr + type->actual_size && !type->members.empty())
                for(auto& m: type->members) {
                    f_addr = m.first->shift(f_addr);
                    if(addr < f_addr) goto bad;
                    if(addr < f_addr + m.first->size) {
                        type = m.first;
                        res.push_back('.');
                        res += m.second;
                        break;
                    }
                    f_addr += m.first->size;
                }
            if(addr < f_addr + type->actual_size) cout << res << '\n';
            else cout << "ERR\n";
            continue;
            bad: cout << "ERR\n";
        }
    }
    for(auto it=types.begin(); it!=types.end(); it++)
        delete it->second;
    return 0;
}

146 lines (4.51KB).

Prefer Object struct for clarity, but optimized code is concise.

Postscript

Algorithms matter, but coding skills are equally crucial! OIers should practice heavy implementation problems to avoid penalties.

Key points for large simulations:

Clear variable names: Avoid unreadable single-letter names.
Use pointers confidently: They simplify type associations.
Structs over arrays: Improve readability when possible.
Readability over micro-optimizations: Unless necessary for time constraints.

Best wishes for NOIP 2023! ~~Please give a like qwq~~