Xếp sách

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
datnvt
Dạng bài
Điểm: 220 Thời gian: 1.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

\(\color{blue}{Tade}\) là một thủ thư làm việc rất chuyên cần ở thư viện \(Abcdef\). Hôm nay, \(\color{blue}{Tade}\) được \(Big Boss\) giao nhiệm vụ sắp xếp lại đống sách mới được gửi đến. Khổ nỗi, \(Boss\) lại yêu cầu \(\color{blue}{Tade}\) sắp xếp \(10^7\) đống sách theo thứ tự không giảm trong vòng \(1s\), mà trong thời gian đó anh ta chỉ có thể sắp xếp được \(10^6\) quyển thôi.

\(\color{blue}{Tade}\) đành phải nhờ đến các bạn lqdcoder giúp đỡ, các bạn hãy giúp anh ấy nhé!

Input

  • Dòng đầu chứa một số tự nhiên \(N (1\le N\le 10^7)\) là số sách mà Tade cần phải sắp xếp.

  • Dòng tiếp theo chứa \(N\) số tự nhiên \(a_i (1\le a_i\le 100)\), là số thứ tự của mỗi quyển sách. Lưu ý, hai quyển sách có thể có cùng một số thứ tự.

Output

  • Một dòng chứa \(N\) số là các số thứ tự được sắp xếp không giảm của \(N\) quyển sách đó.

Example

Test 1

Input 
6
1 5 4 2 3 4
Output 
1 2 3 4 4 5

Bình luận


  • -1
    Bac2010    9:15 a.m. 9 Tháng 10, 2024 ← chỉnh sửa 11

    include <bits/stdc++.h>

    include <vector>

    include <sstream> // Thư viện để sử dụng stringstream

    using namespace std;
    long long n,i,j;
    int main() {
    // Tối ưu hóa nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Bước 1: Đọc N
cin >> n;

// Bước 2: Khai báo vector để lưu số thứ tự sách
vector<int> books(N);

// Bước 3: Đọc số thứ tự sách
for (i = 0; i < n; ++i) {
    cin >> books[i];
}

// Bước 4: Tạo mảng đếm với kích thước 101 (1-100)
vector<int> count(101, 0);

// Bước 5: Cập nhật mảng đếm
for (i = 0; i < n; ++i) {
    count[books[i]]++;
}

// Bước 6: Xuất kết quả vào một chuỗi
stringstream result;
for (i = 1; i <= 100; ++i) {
    for (j = 0; j < count[i]; ++j) {
        result << i << " ";
    }
}

// In ra kết quả
cout << result.str() << endl; // Xuất kết quả một lần

return 0;

    }
    Giải thích:
    Tối ưu hóa I/O: Sử dụng ios::sync_with_stdio(false) và cin.tie(nullptr) để tăng tốc độ nhập và xuất dữ liệu.
    Sử dụng stringstream: Thay vì in trực tiếp từng số, ta sử dụng stringstream để xây dựng chuỗi kết quả và chỉ in một lần. Điều này giúp giảm đáng kể thời gian in cho số lượng lớn dữ liệu.

      • 19 bình luận nữa