Đối chiếu hai pipeline làm sạch record

Bối cảnh

Một nhóm đang thay thế pipeline cũ dùng raw dynamic array bằng phiên bản mới dùng vector. Input gồm n record thô name|code. Cả hai pipeline phải parse đúng một |, trim hai field, chuẩn hóa name thành Title Case với single spaces, uppercase code, bỏ record invalid, rồi sort theo code tăng dần và tie name tăng dần.

Bạn phải chạy hai pipeline độc lập: pipeline A lưu record valid trong raw dynamic pair<string,string>* với capacity doubling; pipeline B dùng vector<pair<string,string>>. Sau sort, so sánh từng record. Nếu giống nhau in MATCH m checksum, rồi danh sách canonical; checksum là tổng độ dài của name|code. Nếu khác, in MISMATCH index.

Bài Advanced tích hợp pointer lifetime, manual reallocation, parsing B21, normalization B20 và comparator M05 nhưng không cần struct/OOP. Điểm khó là giữ hai pipeline độc lập nhưng cùng tuân một specification duy nhất; đó chính là tư duy regression test khi refactor legacy code.

Để regression test có ý nghĩa, pipeline B không được lấy output đã chuẩn hóa từ pipeline A. Cả hai chỉ được chia sẻ specification/hàm pure nếu thiết kế muốn tái sử dụng logic, nhưng storage và quá trình append phải độc lập. Trong dự án thật, cách kiểm thử này giúp phát hiện lỗi migration liên quan đến mất record, sai order hoặc lỗi lifetime mà unit test từng hàm có thể bỏ qua.

Yêu cầu

1. Đọc n raw lines.
2. Pipeline A dùng raw dynamic pair buffer.
3. Pipeline B dùng vector.
4. Cả hai parse/normalize/filter/sort độc lập.
5. So sánh; MATCH thì in count/checksum + records.

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

Không dùng struct/OOP; pipeline raw phải thật sự dùng dynamic array thủ công.

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 n; n dòng record.

Output

MISMATCH index hoặc MATCH m checksum rồi m records.

Ràng buộc

0≤n≤2000, mỗi line ≤500.

Ví dụ 1

Input

5
 nGUYEN van a | k62
Le Thi B|tnut01
bad
Tran C | ab
 |X

Output

MATCH 3 40
Tran C|AB
Nguyen Van A|K62
Le Thi B|TNUT01

Giải thích

Ba record hợp lệ là Nguyen Van A|K62, Le Thi B|TNUT01, Tran C|AB; hai record còn lại invalid. Sort theo code tạo thứ tự AB, K62, TNUT01, nên danh sách là Tran C|AB, Nguyen Van A|K62, Le Thi B|TNUT01. Hai pipeline tạo cùng 3 record. Tổng độ dài ba chuỗi canonical là 40, nên output bắt đầu bằng MATCH 3 40.

Ví dụ 2

Input

0

Output

MATCH 0 0

Giải thích

Với n=0, cả hai pipeline không nhận record nào. Raw state giữ sz=0, cap=0, pointer null; vector cũng rỗng. Không cần sort phần tử thực tế, size hai bên bằng nhau và vòng compare không chạy. Checksum của danh sách rỗng là 0, nên output canonical duy nhất là MATCH 0 0.

Thông tin học tập

• Module: M06
• Buổi: B22
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: raw dynamic pair array, vector pair, parsing, normalization, sort, regression, lifetime
• Giới hạn kiến thức: B01-B22
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100