Xếp sách

Tác giả:

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

0

hkien88 10:10 p.m. 12 Tháng 11, 2024 ← chỉnh sửa 9 →

cứ thêm sort là ko cần thêm thần chú =))

answer full AC

include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n;
cin >> n;
vector<ll> a(n);
for (ll i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a.begin(), a.end());
for (ll i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}

thêm cả ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0); là hết tle =))

0

Youtuber_TWK 1:58 p.m. 16 Tháng 10, 2024

sao sort k dc;v

2 phản hồi

0

quan_vu1 10:23 p.m. 9 Tháng 10, 2024

bựa z, dùng sort phải thêm cả thần chú mới AC

-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.

0

khoidarkgg 10:14 a.m. 14 Tháng 8, 2024

sort ko cần thần chú cx ac 😆

1
scratch_huykhanh 9:46 a.m. 14 Tháng 8, 2024
Solution

Với mỗi số nhập vào, tăng giá trị của nó thêm 1 trong mảng đếm phân phối (tạm gọi mảng đếm phân phối là \(D\)).
For từ \(1\) đến \(100\) (Vì A[i] \(\leq\) \(100\)), với mỗi giá trị i có \(D[i]\)>0, in ra i \(D[i]\) lần (Ví dụ: \(D[3]\) = 5 (Xuất hiện 5 lần) thì in ra 3 3 3 3 3)

\(AC code (Python):\)

limit = 101 #Vì mảng của python bắt đầu từ 0 D = [0]*(limit) N = int(input()) A = list(map(int,input().split())) for i in range(N): D[A[i]]+=1 for i in range(1,limit): print((str(i)+' ')*D[i],end="")
1 phản hồi

2

DaoTrungKien2008 8:37 p.m. 9 Tháng 6, 2024

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Thần chú :)))
Đang TLE 4/5 test, cho vào cái AC luôn