I come to a fun [problem](https://lqdoj.edu.vn/problem/socialised), and after I tried hard to solve it, I curiously to find better algorithm, but I cant.↵
↵
---------- ↵
↵
----------↵
↵
### **The problem is:** ↵
↵
There are $N$ buildings with $a_1, a_2, \dots, a_n$ metters height. These days are hard, the heavy raining weather still not ended yet. In day $d$, every building with height $h$ only have $x_d = \lfloor \frac{h}{d} \rfloor$ height left of good space to use, while others are sunk underwater. Every building having the same value $x_d$ on day $d$ will group together (including $x_d = 0$ which sunk completely underwater) in a way that no other building with same value $x_d$ in another group.↵
↵
----------↵
↵
----------↵
↵
### **The question is:**↵
↵
Output $N$ lines, in each size $s$ from $1$ to $n$, what is the earliest day $d$ that have at least one group of size $s$ (if there is no suitable day then output -1)↵
↵
----------↵
↵
----------↵
↵
↵
### **The constraints are:**↵
↵
- Subtaks 1: $n \leq 100~ and ~a_i \leq 2.10^5$↵
- Subtaks 2: $n \leq 300~ and ~a_i \leq 3.10^6$↵
- Subtaks 3: $n \leq 300~ and ~a_i \leq 5.10^7$↵
↵
↵
----------↵
↵
----------↵
↵
↵
### **The examples are:**↵
↵
<spoiler summary="Example 1">↵
↵
**Input:**↵
↵
```css↵
3↵
1 2 5↵
```↵
↵
↵
**Output:**↵
↵
```css↵
1↵
3↵
6↵
```↵
↵
**Explanation:**↵
↵
Day 1: $x[d] = $ { $ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$ } $=$ { $1, 2, 5$ } — First group of size 1: Any of {$1$} {$2$} {$5$}↵
↵
Day 2: $x[d] = $ { $ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$ } $=$ { $0, 1, 2$ } ↵
↵
Day 3: $x[d] = $ { $ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$ } $=$ { $0, 0, 1$ } — First group of size 2: Only {$1, 2$} ↵
↵
Day 4: $x[d] = $ { $ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 5: $x[d] = $ { $ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 6: $x[d] = $ { $ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$ } $=$ { $0, 0, 0$ } — First group of size 3: Only {$1, 2, 5$}↵
</spoiler>↵
↵
<spoiler summary="Example 2">↵
↵
**Input:**↵
↵
```css↵
3↵
1 1 5↵
```↵
↵
↵
**Output:**↵
↵
```css↵
1↵
1↵
6↵
```↵
↵
**Explanation:**↵
↵
Day 1: $x[d] = $ { $ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$ } $=$ { $1, 1, 5$ } — First group of size 1: Any of {$1$} {$1$} {$5$}↵
↵
Day 2: $x[d] = $ { $ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$ } $=$ { $0, 0, 2$ } — First group of size 2: Only {$1, 1$}↵
↵
Day 3: $x[d] = $ { $ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 4: $x[d] = $ { $ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 5: $x[d] = $ { $ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 6: $x[d] = $ { $ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$ } $=$ { $0, 0, 0$ } — First group of size 3: Only {$1, 2, 5$}↵
</spoiler>↵
↵
↵
<spoiler summary="Example 3">↵
↵
**Input:**↵
↵
```css↵
3↵
2 2 2↵
```↵
↵
↵
**Output:**↵
↵
```css↵
-1↵
-1↵
2↵
```↵
↵
**Explanation:**↵
↵
Day 1: $x[d] = $ { $ \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor$ } $=$ { $2, 2, 2$ } — First group of size 3: Only {$2, 2, 2$}↵
↵
Day 2: $x[d] = $ { $ \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor$ } $=$ { $0, 0, 0$ }↵
↵
Day 3: $x[d] = $ { $ \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor$ } $=$ { $0, 0, 0$ }↵
↵
Day 3 $\leq k \rightarrow \infty$: $x[d] = $ { $ \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor$ } $=$ { $0, 0, 0$ } — There are no group of size 1 and 2↵
</spoiler>↵
↵
-----------↵
↵
-----------↵
↵
### **My approach to this problem:**↵
↵
<spoiler summary="Observation: Harmonic Sequence">↵
↵
We consider this Harmonic Sequence: $S = $ {$\lfloor \frac{n}{x} \rfloor\ |\ x = 1\dots n$} = {$ \lfloor \frac{n}{1} \rfloor, \lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{3} \rfloor, \dots , \lfloor \frac{n}{n - 1} \rfloor , \lfloor \frac{n}{n} \rfloor$}↵
↵
And lets $L$ is Unique Harmonic Sequence. $L = $ {$x\ |\ x \in S$} or/and ($\forall (i \neq j) \in L \rightarrow L_i \neq L_j$) (I will use the set $L$ beneath)↵
↵
Then the number of unique element in array is atmost $2 \sqrt{N}$. Hence $|L| \leq 2 \sqrt{N}$↵
</spoiler>↵
↵
<spoiler summary="Subtask 1: A[i] <= 2 * 10^5">↵
↵
Since day $k > max(a[i])$ will make all array always being as $x[k] =$ {$0, 0, \dots, 0$}, we only need to check for each value $k \in [1, d]$. Then we can calculate how many group of size $s$ in day $k$. My approach is to increase the value $f[\lfloor \frac{a_i}{k} \rfloor] = s$ means in day $\lfloor \frac{a_i}{k} \rfloor$ have group of size $s$, then minimize the first day we have the group of size $s$↵
↵
↵
This approach is $O(n \times max(a_i))$↵
↵
```cpp↵
int main()↵
{↵
int n;↵
cin >> n;↵
↵
vector<int> a(n);↵
for (int &x : a) cin >> x;↵
int k = *max_element(all(a)) + 1;↵
↵
vector<int> f(k + 1, 0);↵
vector<int> q(n + 1, +INF);↵
for (int x = 1; x <= k; ++x) /// Checking possible dividing value↵
{↵
for (int t : a) ++f[t / x]; /// Calculating value f[] for each day [t / x]↵
for (int t : a) minimize(q[f[t / x]], x); /// Minimize first day have group of size k↵
for (int t : a) --f[t / x]; /// Reset the array↵
}↵
↵
for (int i = 1; i <= n; ++i)↵
cout << (q[i] == +INF ? -1 : q[i]) << '\n';↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Subtask 2: A[i] <= 3 * 10^6">↵
↵
Lets $setL$ be a set of good potential $k$ for dividing. Since there are some $k$ that having group of size $s$ but never will be good enough to be the smallest day. That is for each $a_i$, we find all $k$ that have smallest day $d$ that might appear a group of size $\lfloor \frac{a_i}{k} \rfloor$ and insert into $setL$. ↵
↵
The upper bound complexity is $O(n\ \times k\ log(k))$ where $k = |setL| = O(n \times \sqrt{max(a_i)})$ but since $a_i$ is small, and the bigger $n$ is, the more number of duplicate values will all be eliminated by using $set<>$. It would reduce both complexity and constant factor significantly.↵
↵
```cpp↵
int main()↵
{↵
int n;↵
cin >> n;↵
↵
set<int> setL;↵
vector<int> a(n);↵
for (int &x : a)↵
{↵
cin >> x;↵
↵
int sqrtx = sqrt(x);↵
for (int t = 1; t <= sqrt(x); ++t)↵
{↵
setL.insert(x / t + 1);↵
setL.insert(t + 1);↵
}↵
setL.insert(x + 1);↵
setL.insert(1);↵
}↵
↵
vector<int> res(n + 1, +INF);↵
for (int x : setL)↵
{↵
map<int, int> F;↵
for (int t : a) ++F[t / x]; /// Calculating value f[] for each day [t / x]↵
for (int t : a) minimize(res[F[t / x]], x); /// Minimize first day have group of size k↵
}↵
↵
for (int g = 1; g <= n; ++g) cout << (res[g] == +INF ? -1 : res[g]) << '\n';↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Subtask 3: A[i] <= 5 * 10^7">↵
↵
With $T = \sqrt{max(a_i)}$ then all such $k \leq T$ are potential. We only care for such $k > T$ which we can use branch and bound to reduce constant matter.↵
↵
By using map, we can calculate faster by ignoring duplicates. Iterating through map reducing the $O(log)$ factor each query. ↵
↵
Since we solve each potential $k$ from large to smaller, the value $cur$ will be from small to larger, so we dont have to use $min(a, b)$ function, and only update for each $res[x]$ once. We exit when all $N$ query are found or we tried all potential $k$↵
↵
Hence, the complexity is $O(n\ log\ n + n \times (k + \sqrt{max(a_i)}) + k\ log\ k)$ where $k = |setL|$↵
↵
```cpp↵
int n;↵
int cnt = 0;↵
vector<int> a;↵
map<int, int> b;↵
map<int, int>::iterator it;↵
vector<int> res;↵
↵
void out()↵
{↵
for (int i = 1; i <= n; ++i) cout << (res[i] == +INF ? -1 : res[i]) << '\n';↵
exit(0);↵
}↵
void solve(int x)↵
{↵
int sum = 0, val = -1;↵
for (it = b.begin(); it != b.end(); ++it)↵
{↵
int cur = it->first / x;↵
if (cur != val)↵
{↵
val = cur;↵
if (sum && res[sum] == +INF) { res[sum] = x; if (++cnt == n) out(); }↵
sum = 0;↵
}↵
sum += it->second;↵
}↵
if (sum && res[sum] == +INF) { res[sum] = x; if (++cnt == n) out(); }↵
}↵
↵
int main()↵
{↵
cin >> n;↵
a.resize(n);↵
for (int &x : a)↵
{↵
cin >> x;↵
++b[x];↵
}↵
↵
↵
res.assign(n + 1, +INF);↵
int k = ceil(sqrt(*max_element(all(a))));↵
for (int x = 1; x <= k; ++x) solve(x);↵
↵
if (k > 1)↵
{↵
set<int> setL;↵
for (it = b.begin(); it != b.end(); ++it)↵
{↵
int x = it->first;↵
int lim = min(k, x / (k - 1));↵
for (int t = 1; t <= lim; ++t)↵
{↵
int v = x / t + 1;↵
setL.insert(v);↵
}↵
}↵
for (int x : setL) solve(x);↵
}↵
out();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
------------------↵
↵
------------------↵
↵
### My question↵
↵
- Is there a better algorithm for larger $N$ ? (upto $10^4, 10^6$)↵
↵
- Is there a better algorithm for larger $a_i$ ? (upto $10^{12}, 10^{16}, 10^{18}$)↵
↵
- Can I use combinatorics or euclidian algorithm for this problem ?
↵
---------- ↵
↵
----------↵
↵
### **The problem is:** ↵
↵
There are $N$ buildings with $a_1, a_2, \dots, a_n$ metters height. These days are hard, the heavy raining weather still not ended yet. In day $d$, every building with height $h$ only have $x_d = \lfloor \frac{h}{d} \rfloor$ height left of good space to use, while others are sunk underwater. Every building having the same value $x_d$ on day $d$ will group together (including $x_d = 0$ which sunk completely underwater) in a way that no other building with same value $x_d$ in another group.↵
↵
----------↵
↵
----------↵
↵
### **The question is:**↵
↵
Output $N$ lines, in each size $s$ from $1$ to $n$, what is the earliest day $d$ that have at least one group of size $s$ (if there is no suitable day then output -1)↵
↵
----------↵
↵
----------↵
↵
↵
### **The constraints are:**↵
↵
- Subtaks 1: $n \leq 100~ and ~a_i \leq 2.10^5$↵
- Subtaks 2: $n \leq 300~ and ~a_i \leq 3.10^6$↵
- Subtaks 3: $n \leq 300~ and ~a_i \leq 5.10^7$↵
↵
↵
----------↵
↵
----------↵
↵
↵
### **The examples are:**↵
↵
<spoiler summary="Example 1">↵
↵
**Input:**↵
↵
```css↵
3↵
1 2 5↵
```↵
↵
↵
**Output:**↵
↵
```css↵
1↵
3↵
6↵
```↵
↵
**Explanation:**↵
↵
Day 1: $x[d] = $ { $ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$ } $=$ { $1, 2, 5$ } — First group of size 1: Any of {$1$} {$2$} {$5$}↵
↵
Day 2: $x[d] = $ { $ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$ } $=$ { $0, 1, 2$ } ↵
↵
Day 3: $x[d] = $ { $ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$ } $=$ { $0, 0, 1$ } — First group of size 2: Only {$1, 2$} ↵
↵
Day 4: $x[d] = $ { $ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 5: $x[d] = $ { $ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 6: $x[d] = $ { $ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$ } $=$ { $0, 0, 0$ } — First group of size 3: Only {$1, 2, 5$}↵
</spoiler>↵
↵
<spoiler summary="Example 2">↵
↵
**Input:**↵
↵
```css↵
3↵
1 1 5↵
```↵
↵
↵
**Output:**↵
↵
```css↵
1↵
1↵
6↵
```↵
↵
**Explanation:**↵
↵
Day 1: $x[d] = $ { $ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$ } $=$ { $1, 1, 5$ } — First group of size 1: Any of {$1$} {$1$} {$5$}↵
↵
Day 2: $x[d] = $ { $ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$ } $=$ { $0, 0, 2$ } — First group of size 2: Only {$1, 1$}↵
↵
Day 3: $x[d] = $ { $ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 4: $x[d] = $ { $ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 5: $x[d] = $ { $ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$ } $=$ { $0, 0, 1$ } ↵
↵
Day 6: $x[d] = $ { $ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$ } $=$ { $0, 0, 0$ } — First group of size 3: Only {$1, 2, 5$}↵
</spoiler>↵
↵
↵
<spoiler summary="Example 3">↵
↵
**Input:**↵
↵
```css↵
3↵
2 2 2↵
```↵
↵
↵
**Output:**↵
↵
```css↵
-1↵
-1↵
2↵
```↵
↵
**Explanation:**↵
↵
Day 1: $x[d] = $ { $ \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor$ } $=$ { $2, 2, 2$ } — First group of size 3: Only {$2, 2, 2$}↵
↵
Day 2: $x[d] = $ { $ \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor$ } $=$ { $0, 0, 0$ }↵
↵
Day 3: $x[d] = $ { $ \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor$ } $=$ { $0, 0, 0$ }↵
↵
Day 3 $\leq k \rightarrow \infty$: $x[d] = $ { $ \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor$ } $=$ { $0, 0, 0$ } — There are no group of size 1 and 2↵
</spoiler>↵
↵
-----------↵
↵
-----------↵
↵
### **My approach to this problem:**↵
↵
<spoiler summary="Observation: Harmonic Sequence">↵
↵
We consider this Harmonic Sequence: $S = $ {$\lfloor \frac{n}{x} \rfloor\ |\ x = 1\dots n$} = {$ \lfloor \frac{n}{1} \rfloor, \lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{3} \rfloor, \dots , \lfloor \frac{n}{n - 1} \rfloor , \lfloor \frac{n}{n} \rfloor$}↵
↵
And lets $L$ is Unique Harmonic Sequence. $L = $ {$x\ |\ x \in S$} or/and ($\forall (i \neq j) \in L \rightarrow L_i \neq L_j$) (I will use the set $L$ beneath)↵
↵
Then the number of unique element in array is atmost $2 \sqrt{N}$. Hence $|L| \leq 2 \sqrt{N}$↵
</spoiler>↵
↵
<spoiler summary="Subtask 1: A[i] <= 2 * 10^5">↵
↵
Since day $k > max(a[i])$ will make all array always being as $x[k] =$ {$0, 0, \dots, 0$}, we only need to check for each value $k \in [1, d]$. Then we can calculate how many group of size $s$ in day $k$. My approach is to increase the value $f[\lfloor \frac{a_i}{k} \rfloor] = s$ means in day $\lfloor \frac{a_i}{k} \rfloor$ have group of size $s$, then minimize the first day we have the group of size $s$↵
↵
↵
This approach is $O(n \times max(a_i))$↵
↵
```cpp↵
int main()↵
{↵
int n;↵
cin >> n;↵
↵
vector<int> a(n);↵
for (int &x : a) cin >> x;↵
int k = *max_element(all(a)) + 1;↵
↵
vector<int> f(k + 1, 0);↵
vector<int> q(n + 1, +INF);↵
for (int x = 1; x <= k; ++x) /// Checking possible dividing value↵
{↵
for (int t : a) ++f[t / x]; /// Calculating value f[] for each day [t / x]↵
for (int t : a) minimize(q[f[t / x]], x); /// Minimize first day have group of size k↵
for (int t : a) --f[t / x]; /// Reset the array↵
}↵
↵
for (int i = 1; i <= n; ++i)↵
cout << (q[i] == +INF ? -1 : q[i]) << '\n';↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Subtask 2: A[i] <= 3 * 10^6">↵
↵
Lets $setL$ be a set of good potential $k$ for dividing. Since there are some $k$ that having group of size $s$ but never will be good enough to be the smallest day. That is for each $a_i$, we find all $k$ that have smallest day $d$ that might appear a group of size $\lfloor \frac{a_i}{k} \rfloor$ and insert into $setL$. ↵
↵
The upper bound complexity is $O(n\ \times k\ log(k))$ where $k = |setL| = O(n \times \sqrt{max(a_i)})$ but since $a_i$ is small, and the bigger $n$ is, the more number of duplicate values will all be eliminated by using $set<>$. It would reduce both complexity and constant factor significantly.↵
↵
```cpp↵
int main()↵
{↵
int n;↵
cin >> n;↵
↵
set<int> setL;↵
vector<int> a(n);↵
for (int &x : a)↵
{↵
cin >> x;↵
↵
int sqrtx = sqrt(x);↵
for (int t = 1; t <= sqrt(x); ++t)↵
{↵
setL.insert(x / t + 1);↵
setL.insert(t + 1);↵
}↵
setL.insert(x + 1);↵
setL.insert(1);↵
}↵
↵
vector<int> res(n + 1, +INF);↵
for (int x : setL)↵
{↵
map<int, int> F;↵
for (int t : a) ++F[t / x]; /// Calculating value f[] for each day [t / x]↵
for (int t : a) minimize(res[F[t / x]], x); /// Minimize first day have group of size k↵
}↵
↵
for (int g = 1; g <= n; ++g) cout << (res[g] == +INF ? -1 : res[g]) << '\n';↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Subtask 3: A[i] <= 5 * 10^7">↵
↵
With $T = \sqrt{max(a_i)}$ then all such $k \leq T$ are potential. We only care for such $k > T$ which we can use branch and bound to reduce constant matter.↵
↵
By using map, we can calculate faster by ignoring duplicates. Iterating through map reducing the $O(log)$ factor each query. ↵
↵
Since we solve each potential $k$ from large to smaller, the value $cur$ will be from small to larger, so we dont have to use $min(a, b)$ function, and only update for each $res[x]$ once. We exit when all $N$ query are found or we tried all potential $k$↵
↵
Hence, the complexity is $O(n\ log\ n + n \times (k + \sqrt{max(a_i)}) + k\ log\ k)$ where $k = |setL|$↵
↵
```cpp↵
int n;↵
int cnt = 0;↵
vector<int> a;↵
map<int, int> b;↵
map<int, int>::iterator it;↵
vector<int> res;↵
↵
void out()↵
{↵
for (int i = 1; i <= n; ++i) cout << (res[i] == +INF ? -1 : res[i]) << '\n';↵
exit(0);↵
}↵
void solve(int x)↵
{↵
int sum = 0, val = -1;↵
for (it = b.begin(); it != b.end(); ++it)↵
{↵
int cur = it->first / x;↵
if (cur != val)↵
{↵
val = cur;↵
if (sum && res[sum] == +INF) { res[sum] = x; if (++cnt == n) out(); }↵
sum = 0;↵
}↵
sum += it->second;↵
}↵
if (sum && res[sum] == +INF) { res[sum] = x; if (++cnt == n) out(); }↵
}↵
↵
int main()↵
{↵
cin >> n;↵
a.resize(n);↵
for (int &x : a)↵
{↵
cin >> x;↵
++b[x];↵
}↵
↵
↵
res.assign(n + 1, +INF);↵
int k = ceil(sqrt(*max_element(all(a))));↵
for (int x = 1; x <= k; ++x) solve(x);↵
↵
if (k > 1)↵
{↵
set<int> setL;↵
for (it = b.begin(); it != b.end(); ++it)↵
{↵
int x = it->first;↵
int lim = min(k, x / (k - 1));↵
for (int t = 1; t <= lim; ++t)↵
{↵
int v = x / t + 1;↵
setL.insert(v);↵
}↵
}↵
for (int x : setL) solve(x);↵
}↵
out();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
------------------↵
↵
------------------↵
↵
### My question↵
↵
- Is there a better algorithm for larger $N$ ? (upto $10^4, 10^6$)↵
↵
- Is there a better algorithm for larger $a_i$ ? (upto $10^{12}, 10^{16}, 10^{18}$)↵
↵
- Can I use combinatorics or euclidian algorithm for this problem ?
