2019-12-15 22:45:29

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

// ===================================
//   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;

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() {
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;
}
• star
首页