Educational Codeforces Round 98 F問題 - Divide Powers

Source

Educational Codeforces Round 98 F問題
Problem description

問題概要

省略

解法

省略

cLay（version 20201121-1）のコード

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

//no-unlocked
int N, Q, T; ll A[30], X, K;
ll res, tmp[30];
{
  ll i, j, can1, s, cur, nd, pre;

  rd(N,Q,A(N));
  rep(Q){
    rd(T,X,K);
    if(T==1) A[X] = K, continue;

    s = 0;
    rep(i,N) tmp[i] = A[i];
    rep(i,N) s += tmp[i] * (1<<i);
    if(s < K) wt(-1), continue;

    rep(i,X+1) K -= tmp[i];
    K >?= 0;

    res = ll_inf;
    cur = 0;
    can1 = 0;
    rep(i,1,X+1) can1 += tmp[i] * ((1<<i) - 1);
    if(can1 >= K) res <?= cur + K;

    while(K > 0){
      rep(i,X+1,N){
        j = min(K / (1<<(i-X)), tmp[i]);
        tmp[i] -= j;
        K -= j * (1 << (i-X));
        cur += j * ((1 << (i-X)) - 1);
        can1 += j * (1 << (i-X)) * ((1 << X) - 1);
        if(can1 >= K) res <?= cur + K;

        if(tmp[i]){
          if(i==X+1){
            K = 0;
            cur++;
            res <?= cur + K;
            break;
          }
          cur++;
          tmp[i]--;
          tmp[i-1]+=2;
          break;
        }
      }
      if(i==N) break;
    }

    wt(res);
  }
}

Current time: 2024年04月26日21時49分19秒
Last modified: 2020年11月21日19時18分09秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)