yukicoder No.911 - ラッキーソート

Source

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

問題概要

省略

解法

省略

cLay（version 20191102-1）のコード

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

int N; ll LL, RR;
ll A[2d5];

int cond[62];
int L[62], R[62];

void doit(int k, int a, int b){
  int mn0, mx0, mn1, mx1;
  if(k < 0) return;
  mn0 = mn1 = int_inf;
  mx0 = mx1 = -int_inf;
  rep(i,a,b+1){
    if(A[i] & (1LL<<k)){
      mn1 <?= i;
      mx1 >?= i;
    } else {
      mn0 <?= i;
      mx0 >?= i;
    }
  }
  if(mn0 == int_inf || mn1 == int_inf) doit(k-1, a, b), return;
  if(mx0 < mn1){
    cond[k] |= 2;
    doit(k-1, a, mx0);
    doit(k-1, mn1, b);
  } else if(mx1 < mn0){
    cond[k] |= 1;
    doit(k-1, a, mx1);
    doit(k-1, mn0, b);
  } else {
    cond[k] |= 3;
  }
}

ll dp[2][2][62];
ll solve(int x, int y, int d){
  ll res = 0;
  if(d < 0) return 1;
  if(dp[x][y][d] >= 0) return dp[x][y][d];
  if(!BIT_ith(cond[d],0) && (L[d]==0 || x)) res += solve(x, if[R[d]==1,1,y], d-1);
  if(!BIT_ith(cond[d],1) && (R[d]==1 || y)) res += solve(if[L[d]==0,1,x], y, d-1);
  return dp[x][y][d] = res;
}

{
  rd(N,LL,RR,A(N));
  rep(i,62) if(LL&(1LL<<i)) L[i] = 1;
  rep(i,62) if(RR&(1LL<<i)) R[i] = 1;
  doit(61, 0, N-1);
  rep(i,2) rep(j,2) rep(k,62) dp[i][j][k] = -1;
  wt(solve(0,0,61));
}

Current time: 2024年04月23日21時08分59秒
Last modified: 2019年11月02日11時41分14秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)