保存されている過去のバージョンの一覧

AtCoder Beginner Contest 143 F問題 - Distinct Numbers

Source

AtCoder Beginner Contest 143
問題文

問題概要

省略

解法

省略

cLay（version 20191027-1）のコード

C++に変換後のコードはこちら

int N, A[3d5];
int arr[3d5], res[3d5];
int sz, num[3d5], len[3d5];
{
  int k, x;
  rd(N,(A--)(N));
  rep(i,N) arr[A[i]]++;
  rsortA(N,arr);

  sz = runLength(N, arr, num, len);
  rrep(i,N){
    k = res[i] = num[sz-1];
    len[sz-1]--;
    if(len[sz-1]==0) sz--;
    if(i==0) break;
    while(k > 0){
      x = k / len[sz-1];
      if(sz>=2) x <?= num[sz-2] - num[sz-1];
      if(x || (sz>=2 && num[sz-2]==num[sz-1])){
        k -= len[sz-1] * x;
        num[sz-1] += x;
        if(sz>=2 && num[sz-2] == num[sz-1]){
          len[sz-2] += len[sz-1];
          sz--;
        }
      } else {
        num[sz] = num[sz-1];
        len[sz] = len[sz-1] - k;
        num[sz-1]++;
        len[sz-1] = k;
        k = 0;
        sz++;
      }
    }
  }
  wtLn(res(N));
}

Current time: 2024年04月26日18時18分33秒
Last modified: 2019年11月01日20時24分04秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC143 ABC_F
トップページに戻る

Logged in as: unknown user (not login)