You are given 𝑛 integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the 𝑛 numbers may not be chosen.

A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different.

What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.

#### 链接🔗

「CodeForces 1277F」Beautiful Rectangle

#### 代码

const ll maxd = 4e5+10;

ll cnt[maxd],n,ans[maxd];
map<ll,ll> mp;
vector<P> a;
bool cmp(const P a,const P b)
{
return a.ND > b.ND;
}
int main()
{
//    __IN;__OUT;
RLL(n);
FOR(i,1,n)
{
ll x;RLL(x);
mp[x]++;
}
for(auto p:mp) a.pb(p);
sort(all(a),cmp);
for(auto x:a) cnt[x.ND]++;

//确定行数和最大摆放数量
ll now = a.size(),mx = 0,row = 0, sum = 0;
for(int i=1;i *i<=n;i++)
{
sum+= cnt[i] * i;
now -= cnt[i];
ll t = now * i + sum;
if(t < i * i) continue; // 数不够
if(t / i * i > mx) mx = t/i*i,row = i; //如果选出的最大数量多于当前值，则更新
}
// 构造方案
ll col = mx / row , x = 1, y =1;
FOR(i,1,a.size())
{
ll num = min(row,a[i-1].ND);
while(num--)
{
ans[(x-1)*col + y] = a[i-1].first;
x = (x %row) + 1, y = (y%col) + 1;
if(ans[(x-1) * col + y]) y = (y%col) + 1;
}
}
PLN(mx);PLP(row); PLN(col);
FOR(i,1,row)
FOR(j,1,col)
if(j== col)  PLN(ans[(i-1) * col +j]);
else PLP(ans[(i-1) * col +j]);
return 0;
}