yukicoder No.854 - 公平なりんご分配

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

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

int N, A[1d5];

int Q, P[1d5], L[1d5], R[1d5];
int res[1d5];

int ok[100001], fc[100001];

int ps, prm[1000];
int cnt[1d5];

{
  int i, j, k;
  
  ps = Prime(2000, prm);

  rd(N,A(N),Q,(P,L--,R)(Q));
  rep(i,Q) res[i] = 1;

  rep(i,N) if(A[i]==0) ok[i+1] = 1;

  rep(i,N) ok[i+1] += ok[i];
  rep(i,Q) if(ok[R[i]]-ok[L[i]]){ res[i] = 2; continue; }

  rep(k,ps){
    j = 0;
    rep(i,Q) if(res[i]==1){
      cnt[i] = 0;
      while(P[i]%prm[k]==0) P[i] /= prm[k], cnt[i]++, j++;
    }
    if(j==0) continue;

    rep(i,N+1) fc[i] = 0;
    rep(i,N){
      if(ok[i+1]-ok[i]) continue;
      while(A[i]%prm[k]==0) A[i] /= prm[k], fc[i+1]++;
    }
    rep(i,N) fc[i+1] += fc[i];

    rep(i,Q) if(res[i]==1){
      if(fc[R[i]]-fc[L[i]] < cnt[i]) res[i] = 0;
    }
  }

  rep(i,Q) if(res[i]==1 && P[i] > 1) res[i] = 0;

  rep(i,Q) wt(if[res[i],"Yes","NO"]);
}

Current time: 2024年04月27日03時17分39秒
Last modified: 2019年08月21日06時07分30秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)