Wondering if I can optimize my algorithm

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

I come to a fun problem, 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:

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:

$$$N \leq 300$$$
$$$a_i \leq 10^9$$$

The examples are:

Example 1

Input:

3
1 2 5

Output:

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$$$}

Example 2

Input:

3
1 1 5

Output:

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$$$}

Example 3

Input:

3
2 2 2

Output:

-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

Rev.	By	When	Δ	Comment
en17	SPyofgame	2020-11-28 11:53:17	1	Tiny change: '----------\n\n------' -> '---------- \n\n------'
en16	SPyofgame	2020-11-28 11:52:43	587
en15	SPyofgame	2020-11-23 08:27:18	1	Tiny change: 'nificantly\n\n```cpp' -> 'nificantly.\n\n```cpp'
en14	SPyofgame	2020-11-12 20:11:18	4
en13	SPyofgame	2020-11-10 17:15:42	71
en12	SPyofgame	2020-11-10 10:12:24	28	Tiny change: ' cant.\n\n### ' -> ' cant.\n\n----------\n\n----------\n\n### '
en11	SPyofgame	2020-11-09 18:34:14	43
en10	SPyofgame	2020-11-09 18:33:31	106
en9	SPyofgame	2020-11-09 18:23:14	222
en8	SPyofgame	2020-11-08 20:55:42	2	Tiny change: '$a_i \leq 3 * 10^7$\n' -> '$a_i \leq 5 * 10^7$\n'
en7	SPyofgame	2020-11-08 20:43:41	6	Tiny change: '$a_i \leq 10^9$\n\n\n---' -> '$a_i \leq 3 * 10^7$\n\n\n---'
en6	SPyofgame	2020-11-08 20:13:13	249
en5	SPyofgame	2020-11-08 20:10:58	923	Tiny change: 'ty is $O(n log n \times ' -> 'ty is $O(n\ log\ n + n \times ' (published)
en4	SPyofgame	2020-11-08 19:44:15	4420
en3	SPyofgame	2020-11-08 18:42:32	3161	Tiny change: ': $x[d] = {\lfloor \' -> ': $x[d] = \{\lfloor \'
en2	SPyofgame	2020-11-02 19:58:26	186
en1	SPyofgame	2020-10-28 15:51:50	865	Initial revision (saved to drafts)

The problem is:

The question is:

The constraints are:

The examples are:

My approach to this problem:

History