## KHUYÊN CÁC BẠN NÊN SUY NGHĨ TRƯỚC KHI ĐỌC SOLUTION NHAAA
## Ý tưởng
- Với mỗi xe i, ta bắt đầu từ p[i], nếu ô đó đã có người ta xét tiếp đến (p[i] + 1) % n, (p[i] + 2) % n, ...
đến khi tìm được ô trống.
Có thể thấy duyệt trâu như thế sẽ tốn **O(n)** cho mỗi xe dẫn đến độ phức tạp tổng lên đến **O(n \* n)**
dẫn đến **TLE**
- Ta có thể "nhảy" thẳng đến ô trống tiếp theo mà không cần duyệt trâu bằng cách dùng cấu trúc dữ liệu
**DSU**. Ta coi mỗi ô là một node trong **DSU**, và parent của mỗi node sẽ trỏ đến ô trống tiếp theo. Sau khi
ô **k** đã bị chiếm thì ta gộp **k** với **k + 1**.
## Hướng giải
- Gọi parent[i] là ô trống tiếp theo nếu muốn đậu ở điểm i.
- Ban đầu parent[i] = i, mọi ô đều trống nên i trỏ tới i
- Khi có xe muốn đậu tại k, ta tìm ô bằng cách gọi get_parent(k)
- Sau khi ô đó bị chiếm ta gộp parent[k] và parent[k + 1]
- Lặp lại cho mỗi xe
## CODE
### `[ARE YOU SURE YOU WANT TO PROCEED]`
```
/*
"I'm not sure I should even call it parent..."
- KevinPhan 19/06/2025 -
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
bool taken[100009];
int parent[100009], sz[100009];
int get_parent(int u)
{
if (u == parent[u]) return parent[u];
return parent[u] = get_parent(parent[u]);
}
bool join(int u, int v)
{
u = get_parent(u);
v = get_parent(v);
if (sz[u] < sz[v]) swap(u, v);
if (u == v) return false;
sz[u] += sz[v];
parent[v] = u;
return true;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) parent[i] = i, sz[i] = 1;
for (int i = 1; i <= n; i++)
{
int k;
cin >> k;
k = get_parent(k);
cout << k << ' ';
parent[k] = parent[k % n + 1];
}
return 0;
}
```
kevinPhan
Created at
0 likes