#include using namespace std; struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(13); } }init; using ll = long long; using ull = unsigned long long; using pii = pair; using pll = pair; template using minpq=priority_queue,greater>; #define rep(i, x, limit) for(int i=(x); i< (limit); ++i) #define REP(i, x, limit) for(int i=(x); i<=(limit); ++i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define el '\n' #define spa ' ' #define Yes cout<<"Yes"< std::ostream &operator<< (std::ostream &os, std::pair p){ os << "{" << p.first << "," << p.second << "}"; return os; } template inline bool chmin(T1 &a,T2 b){return a>b?a=b,true:false;} template inline bool chmax(T1 &a,T2 b){return a=0); if(a==0 and b==0) return 1; if(a==1) return 1; if(a==-1) return (b&1)?-1:1; ll res=1; while(b){ if(b&1) res*=a; b>>=1; if(b) a*=a; } return res; } // 配列の要素を空白区切りで出力 第二引数をtrueにすると改行区切り template inline void print_vec(const vector &v, bool split_line=false) { if(v.empty()){ cout << "This vector is empty." << el; return; } constexpr bool isValue = is_integral::value; for (int i = 0; i < (int)v.size(); i++) { if constexpr(isValue){ if((v[i]==inf) || (v[i]==infl)) cout << 'x' << " \n"[split_line || i+1==(int)v.size()]; else cout << v[i] << " \n"[split_line || i+1==(int)v.size()]; }else cout << v[i] << " \n"[split_line || i+1==(int)v.size()]; } } // Pythonのenumerateみたいなやつ [index,value]を範囲for文に提供 template inline vector> enumerate(const vector &v){ vector> res(ssize(v)); for(int i=0;i> enumerate(const string &s){ vector> res(ssize(s)); for(int i=0;i vector multipleSort(Compare comp = Compare(), Vectors&... vectors) { const size_t size = std::get<0>(std::tie(vectors...)).size(); ((void)std::initializer_list{(vectors.size() == size ? 0 : throw std::invalid_argument("Vectors must have the same size"))...}); std::vector indices(size); std::iota(indices.begin(), indices.end(), 0); std::sort(indices.begin(), indices.end(), [&](size_t i, size_t j) { return comp(std::get<0>(std::tie(vectors...))[i], std::get<0>(std::tie(vectors...))[j]); }); auto reorder = [&](auto& vec) { auto temp=vec; for (size_t i = 0; i < size; ++i) { vec[i] = temp[indices[i]]; } }; (reorder(vectors), ...); return indices; } // エラトステネスの篩, 1以上N以下の整数について素数かどうか判定する vector Eratosthenes(ll N) { vector isprime(N + 1, true); isprime[0] = isprime[1] = false; for (int p = 2; p <= N; p++) { if (!isprime[p]) continue; for (int q = p * 2; q <= N; q += p) { isprime[q] = false; } } return isprime; } // 1以上N以下の素数を格納したvectorを返す,Eratosthenes関数と併せて使う vector get_primes(ll N){ vector eratosthenes = Eratosthenes(N); vector primes; for(ll i = 2; i <= N; i++){ if(eratosthenes[i]) primes.emplace_back(i); } return primes; } // 二分探索による、浮動小数点型を介さないsqrt // 制約:0 <= x <= LLONG_MAX ll ll_sqrt(ll x){ assert(0 <= x); ll ok = 0, ng = x/2+2; while(abs(ok-ng) > 1){ ll mid = (ok+ng)/2; if(x/mid < mid) ng = mid; else ok = mid; } return ok; } int main(){ /*//-------------------------------------------------------- 極力生地iはAiで焼きたいよなぁ 初期解をそう置いたうえで、T秒のを許容して改善できるか考える? Aiの頻度配列を取ると、初期解の時間はmax(cnt)に一致 じゃあそれを分配していけないかって話になりそう 1:5,2:1 -> 1:4,2:1+1*2 -> 1:3,2:1+2*2 つまりボトルネックなオーブンから一個取って一番余裕なオーブンに渡す んで改善するかを見ればよい よしなにやれば間に合いそう 本当に間に合うのか?あれ 怪しくないか?逆転しないのはそうだけどO(N^2)になりうらないか あ 答えを二分探索じゃないか? K分以下にできるかとすると、O(N)かけて判定していける気がする cnt[Ai]>K だったら? cnt[Ai]個だけ焼かせて、K-cnt個残るね 負債はどこで支払っても等価なので、個数だけ管理しておけばいいんじゃないかな 返済できる個数と、負債の個数とで *///-------------------------------------------------------- ll N,M,T; cin>>N>>M>>T; vector A(M); rep(i,0,M) cin>>A[i]; vector cnt(N,0); rep(i,0,M) cnt[A[i]-1]++; ll ok=T*M,ng=0; while(abs(ok-ng)>1){ ll K=midpoint(ng,ok); ll val=0; rep(i,0,N){ if(cnt[i]>=K){ val-=cnt[i]-K; }else{ val+=(K-cnt[i])/T; } } if(val>=0) ok=K; else ng=K; } cout<