AtCoder Grand Contest 029 C問題 - Lexicographic constraints

Source

AtCoder Grand Contest 029
問題文

問題概要

省略

解法

省略

cLayversion 20190925-1)のコード

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

int N, A[2d5];
int s[2d5], v[2d5], sz;

int add(int k, int z){
  if(k==0) return 0;
  
  if(sz==0 || s[sz-1] < k){
    s[sz] = k;
    v[sz++] = 1;
    return 1;
  }
  v[sz-1]++;
  if(v[sz-1]==z){
    sz--;
    return add(k-1,z);
  }
  return 1;
}

{
  int i, res;
  rd(N,A(N));
  res = bsearch_min[int,z,1,N][
    sz = 0;
    rep(i,1,N){
      if(A[i-1] < A[i]) continue;
      while(sz && s[sz-1] > A[i]) sz--;
      if(z==1) break;
      if(!add(A[i],z)) break;
    }
  ](i==N);
  wt(res);
}

Current time: 2021年09月24日23時20分33秒
Last modified: 2019年09月26日02時52分20秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC029 AGC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: