Codeforces

Luogu

分析

考虑枚举短边的长度 $r$。设数 $i$ 有 $cnt_i$ 个，那么我们至多能填

$$s_r=\sum_i\min\left\{cnt_i,r\right\}$$

个数到矩形中。因此当短边长度为 $r$ 时长边至多为 $\left\lfloor\frac{s_r}{r}\right\rfloor$。

因为短边长度不超过 $\sqrt{n}$，因此我们可以在 $\mathcal{O}(n\sqrt{n})$ 的时间内求出答案。

现在我们仅需要构造一组方案了。我们对于每个数 $i$ 都拿 $\min\left\{cnt_i,ansr\right\}$ 个出来构成一个序列。这个序列需要满足相同的数放在一起，并且恰好序列中数量恰好等于 $ansr$ 的数放在最前面。这个序列很容易构造出来，只要把所有数按出现次数从大到小排个序就好了。

这样子我们只要斜着枚举每个格子，并按顺序把序列中的数放上去即可。正确性比较显然。

具体实现和细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

int n;
int a[N],S[N],cnt[N];
vector<pair<int,int> > vec;
vector<int> num;
vector<vector<int> > ans;

int main() {
    n=read();
    for (re int i=1;i<=n;++i) S[i]=a[i]=read();
    sort(S+1,S+n+1); int m=unique(S+1,S+n+1)-S-1;
    for (re int i=1;i<=n;++i) a[i]=lower_bound(S+1,S+m+1,a[i])-S;

    for (re int i=1;i<=n;++i) ++cnt[a[i]];
    for (re int i=1;i<=m;++i) vec.push_back(make_pair(cnt[i],i));
    sort(vec.begin(),vec.end());
    int ansS=0,ansr,ansc;
    for (re int r=1;r*r<=n;++r) { int s=0;
        for (auto j:vec) s+=min(j.first,r);
        int c=s/r;
        if (c<r) continue;
        if (r*c>ansS) ansS=r*c,ansr=r,ansc=c;
    }
    printf("%d\n%d %d\n",ansS,ansr,ansc);

    reverse(vec.begin(),vec.end());
    for (auto i:vec) {
        for (re int j=1;j<=min(ansr,i.first);++j)
            num.push_back(i.second);
    }
    ans.resize(ansr);
    for (re int i=0;i<ansr;++i) ans[i].resize(ansc);
    for (re int i=0,x=0,y=0;i<ansS;++i) {
        ans[x][y]=num[i]; ++x,++y;
        if (x==ansr) x=0,y-=ansr-1;
        if (y<0) y+=ansc;
        if (y>=ansc) y-=ansc;
    }
    for (re int i=0;i<ansr;++i) {
        for (re int j=0;j<ansc;++j) printf("%d ",S[ans[i][j]]);
        puts("");
    }
    return 0;
}