Hướng dẫn giải của Bedao Regular Contest 08 - BOOKS


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Subtask #1

Gọi ~a~ là mảng có chứa phần tử được sắp xếp tăng dần từ ~1~ đến ~n~. Với mỗi ~x~, chuyển phần tử ~a[x]~ lên đầu mảng ~a~.

Độ phức tạp: ~O(n \times q)~

Subtask #2

Đánh dấu những quyển sách đã bị lấy ra và thêm các giá trị ~x~ vào một mảng.

Duyệt ngược mảng đó, in ra những phần tử xuất hiện lần đầu trong mảng. Sau đó, in ra số hiệu của những quyển sách chưa được lấy ra theo thứ tự tăng dần.

Độ phức tạp: ~O(q+n)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, a[100005], q;
bool chosen[100005], selected[100005];
void solve()
{
    memset(selected, false, sizeof selected);
    memset(chosen, false, sizeof chosen);
    cin >> n >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> a[i];
        chosen[a[i]] = true;
    }
    for(int i = q; i >= 1; i--)
    {
        if(selected[a[i]] == false)
        {
            cout << a[i] << endl;
            selected[a[i]] = true;
        }
    }
    for(int i = 1; i <= n; i++) if(chosen[i] == false) cout << i << endl;
}  

int main() {
    solve();
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.