Bộ đệm co giãn thủ công

Bối cảnh

Bạn phải cài một bộ đệm số nguyên đơn giản giống "phiên bản thu nhỏ" của vector, nhưng chỉ dùng raw pointer và new[]/delete[]. Bộ đệm ban đầu rỗng, size=0, capacity=0. Hệ thống nhận q lệnh:

• PUSH x: thêm x vào cuối. Nếu size==capacity, phải cấp phát vùng nhớ mới với capacity 1 nếu đang 0, ngược lại gấp đôi; copy dữ liệu cũ, delete[] vùng cũ rồi chuyển pointer.
• POP: nếu không rỗng, bỏ phần tử cuối; capacity không giảm.
• SET i x: nếu i hợp lệ, gán phần tử.
• GET i: in giá trị hoặc OUT_OF_RANGE.
• INFO: in size capacity sum.

Bài Advanced buộc người học quản lý ownership và lifetime qua nhiều lần reallocation. Invariant quan trọng là 0≤size≤capacity; pointer chỉ sở hữu đúng vùng nhớ hiện tại. Sau khi copy sang buffer mới, vùng cũ phải được giải phóng đúng một lần và không được dùng lại. sum được duy trì để INFO O(1), tạo thêm một state cần đồng bộ.

Khi tự kiểm tra lời giải, hãy theo dõi ba snapshot sau mỗi lệnh: size, capacity và địa chỉ buffer hiện tại. Sau một lần reallocation, địa chỉ có thể đổi nhưng toàn bộ prefix dữ liệu hợp lệ phải giữ nguyên. Đây chính là khác biệt giữa identity của vùng nhớ và identity của container logic. Việc hiểu điều này giúp học viên tránh gắn logic chương trình vào một địa chỉ cũ đã hết lifetime.

Yêu cầu

1. Khởi tạo buffer rỗng.
2. Xử lý PUSH/POP/SET/GET/INFO đúng semantics.
3. Reallocate theo capacity doubling.
4. Duy trì sum nhất quán.
5. Cuối chương trình delete[] vùng nhớ cuối cùng.

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

Không dùng vector hoặc smart pointer.

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 lệnh.

Output

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

Ràng buộc

1≤q≤5000, index 0-based, mọi tổng trong long long.

Ví dụ 1

Input

12
INFO
PUSH 5
PUSH 7
INFO
PUSH 9
GET 1
SET 1 10
INFO
POP
INFO
GET 2
GET 1

Output

0 0 0
2 2 12
7
3 4 24
2 4 15
OUT_OF_RANGE
10

Giải thích

Ban đầu INFO in 0 0 0. PUSH5 tạo capacity1; PUSH7 cần reallocate lên 2. INFO lúc này là size2 cap2 sum12. PUSH9 làm cap tăng 4. GET1 trả 7; SET1=10 tăng sum thêm 3, nên INFO là 3 4 24. POP bỏ 9, còn 2 4 15. GET2 vượt size nên OUT_OF_RANGE; GET1 trả 10.

Ví dụ 2

Input

7
PUSH 1
POP
POP
INFO
GET 0
PUSH 2
INFO

Output

0 1 0
OUT_OF_RANGE
1 1 2

Giải thích

PUSH1 tạo buffer size1 cap1, sau đó POP đưa size về0 nhưng capacity vẫn1. POP thêm lần nữa không làm gì. INFO là 0 1 0; GET0 out-of-range vì size=0. PUSH2 tái sử dụng capacity1, cuối INFO 1 1 2. Ví dụ phân biệt rõ size với capacity.

Thông tin học tập

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