Danh sách chuỗi co giãn theo lệnh

Bối cảnh

Hãy xây một danh sách string co giãn thủ công, không dùng vector làm storage. State gồm raw pointer, size, capacity. Hệ thống hỗ trợ:

• PUSH text: thêm text ở cuối.
• INSERT i text: chèn trước index i nếu 0≤i≤size.
• ERASE i: xóa phần tử hợp lệ và dịch trái.
• SET i text: gán.
• GET i: in text hoặc OUT_OF_RANGE.
• INFO: in size capacity totalLength.

Khi thêm phần tử và hết capacity, reallocate theo doubling như B19 nhưng phần tử là std::string, nghĩa là copy/gán phải xảy ra trước delete[] buffer cũ. totalLength phải đồng bộ với PUSH/INSERT/ERASE/SET để INFO O(1). Bài Advanced kết hợp ownership raw, thao tác dịch phần tử và input getline cho command chứa space.

Đây là bước nâng đáng kể so với buffer số ở B19: mỗi phần tử tự quản lý bộ nhớ nội bộ của std::string, nhưng mảng chứa chúng vẫn do bạn sở hữu thủ công. Vì vậy reallocation sai thứ tự có thể làm mất cả batch chuỗi.

Hãy đặc biệt chú ý thao tác INSERT: sau khi đảm bảo capacity, phần tử phải được dịch từ cuối về vị trí i; nếu dịch từ i lên trên, dữ liệu nguồn sẽ bị ghi đè trước khi được copy. Với ERASE thì hướng dịch ngược lại. Đây là ví dụ rõ ràng cho việc cùng một mảng nhưng hướng copy phụ thuộc vùng nguồn/đích chồng lấn.

Yêu cầu

1. Cài raw dynamic string list.
2. Capacity doubling khi cần.
3. Hỗ trợ 6 command.
4. Duy trì totalLength.
5. GET/INFO tạo output; cleanup cuối.

Yêu cầu tổ chức code

Không dùng vector làm storage chính.

Online Judge chấm output. Giảng viên có thể review source code để kiểm tra việc sử dụng đúng pointer/lifetime/string pipeline theo phạm vi buổi học.

Input

Dòng 1 q; q dòng command.

Output

Mỗi GET/INFO một dòng.

Ràng buộc

1≤q≤3000, tổng độ dài input ≤1e6.

Ví dụ 1

Input

12
INFO
PUSH hello world
PUSH abc
INFO
INSERT 1 X Y
GET 1
SET 0 hi
INFO
ERASE 1
GET 1
INFO
GET 5

Output

0 0 0
2 2 14
X Y
3 4 8
abc
2 4 5
OUT_OF_RANGE

Giải thích

INFO đầu là 0 0 0. PUSH hello world tạo cap1, PUSH abc reallocate cap2; INFO 2 2 14. INSERT index1 X Y cần cap4 và tạo thứ tự hello world, X Y, abc; GET1 in X Y. SET0=hi làm total từ 17 xuống 8. ERASE1 bỏ X Y, GET1 lúc này là abc; INFO 2 4 5; GET5 out-of-range.

Ví dụ 2

Input

7
PUSH a
ERASE 0
ERASE 0
INFO
INSERT 0 hello
GET 0
INFO

Output

0 1 0
hello
1 1 5

Giải thích

Sau PUSH a, list có size1 cap1 total1. ERASE 0 chỉ giảm size về0 và total về0, capacity vẫn1; lệnh ERASE tiếp theo bị bỏ vì index không hợp lệ. INFO vì thế in 0 1 0. INSERT 0 hello dùng lại buffer hiện có, size1 total5; GET0 trả hello và INFO cuối 1 1 5.

Thông tin học tập

• Module: M06
• Buổi: B22
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: raw dynamic string array, capacity doubling, insert erase, lifetime, command simulation
• Giới hạn kiến thức: B01-B22
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100