1. Tóm tắt đề bài

Cho ~K~ dãy số nguyên, mỗi dãy có độ dài ~L_i~ bất kỳ. Hãy gom toàn bộ các dãy này thành một vector duy nhất, loại bỏ tất cả các phần tử trùng lặp và sắp xếp theo thứ tự tăng dần.

• Dữ liệu vào (Input):
  • Dòng 1: Số nguyên ~K~ (~1 \le K \le 10^4~).
  • ~K~ cụm dòng tiếp theo: Mỗi cụm dòng gồm 2 dòng:
    • Dòng đầu chứa số nguyên ~L_i~ (số lượng phần tử của dãy thứ ~i~).
    • Dòng sau chứa ~L_i~ số nguyên của dãy đó.
  • Giới hạn: Tổng số lượng phần tử của tất cả các dãy ~\sum L_i \le 2 \times 10^5~.
• Dữ liệu ra (Output):
  • Dòng 1: Một số nguyên duy nhất là số lượng phần tử độc nhất (không trùng lặp).
  • Dòng 2: Dãy số sau khi đã sắp xếp tăng dần và loại bỏ trùng lặp, các số cách nhau bởi một khoảng trắng.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • Số lượng dãy: ~K \le 10^4~.
  • Tổng số phần tử cần xử lý: ~M = \sum L_i \le 2 \times 10^5~.
  • Giá trị các số nguyên nằm trong phạm vi kiểu số nguyên 32-bit (int).

• Đánh giá thuật toán & Cấu trúc dữ liệu:

  • Có hai hướng xử lý phổ biến:
    1. Cách 1 (Dùng std::vector kết hợp sort và unique): Đọc tất cả ~M~ phần tử đưa vào một vector, sau đó dùng sort để sắp xếp tăng dần, tiếp theo dùng hàm unique kèm lệnh erase để lọc bỏ các phần tử trùng nhau.
       • Độ phức tạp thời gian: ~\mathcal{O}(M \log M) \approx 2 \times 10^5 \times 18 \approx 3.6 \times 10^6~ phép tính. Chạy cực nhanh (~< 0.05~ giây).
    2. Cách 2 (Lọc thủ công sau khi sort): Sau khi sắp xếp vector tăng dần, ta duyệt từ đầu đến cuối và chỉ gom các phần tử khác với phần tử đứng liền trước nó.
  • Cả hai cách đều tối ưu tuyệt đối về thời gian và bộ nhớ. Cách dùng bộ đôi std::unique và erase trên vector là phương pháp chuẩn mực, đúng theo yêu cầu dùng vector của đề bài.

3. Thuật toán xử lý

• Cấu trúc lưu trữ:

  • Khai báo một mảng động: vector<int> a;.

• Các bước thực hiện:

  1. Khai báo biến ~k~. Nhập số lượng dãy bằng lệnh chuẩn: cin >> k;.
  2. Dùng vòng lặp ~i~ chạy từ ~1~ đến ~k~:
     • Nhập số phần tử của dãy hiện tại: cin >> n; (với ~n = L_i~).
     • Dùng vòng lặp ~j~ chạy từ ~1~ đến ~n~: đọc từng giá trị ~x~ và đẩy trực tiếp vào cuối vector bằng a.push_back(x);.
  3. Sắp xếp toàn bộ vector ~a~ tăng dần:
     • sort(a.begin(), a.end());
  4. Loại bỏ các phần tử trùng lặp liền kề nhau:
     • Sử dụng câu lệnh kết hợp chuẩn trong C++: a.erase(unique(a.begin(), a.end()), a.end());
     • Giải thích: Hàm unique sẽ dồn các phần tử độc nhất về nửa đầu vector và trả về con trỏ (iterator) tại vị trí phần tử rác đầu tiên. Hàm erase sẽ xóa toàn bộ các phần tử dư thừa từ vị trí đó đến hết vector.
  5. In kết quả:
     • Dòng 1: In số lượng phần tử còn lại bằng a.size() và xuống dòng bằng cout << endl;.
     • Dòng 2: Duyệt từng phần tử trong vector a từ chỉ số ~0~ đến a.size() - 1 để in ra các giá trị cách nhau dấu cách, kết thúc bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(M \log M)~ với ~M = \sum L_i \le 2 \times 10^5~, thời gian thực thi ~< 0.05~ giây.
  • Không gian (bộ nhớ): ~\mathcal{O}(M)~ — Bộ nhớ tiêu tốn khoảng vài MB, hoàn toàn an toàn trong giới hạn bộ nhớ tiêu chuẩn (256 MB).

4. Mã nguồn cài đặt (C++)

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

int main() {
    // Tối ưu tốc độ vào/ra chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int k;
    cin >> k;

    vector<int> a;

    // Đọc k cụm dữ liệu
    for (int i = 1; i <= k; i++) {
        int n;
        cin >> n;
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            a.push_back(x);
        }
    }

    // Sắp xếp các phần tử tăng dần
    sort(a.begin(), a.end());

    // Loại bỏ các phần tử trùng lặp liên tiếp
    a.erase(unique(a.begin(), a.end()), a.end());

    // In số lượng phần tử độc nhất
    cout << a.size() << endl;

    // In các phần tử đã sắp xếp và lọc trùng
    for (int i = 0; i < (int)a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}