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

Codeforces Round #694 DIV1 E問題 - Strange Permutation

Source

Codeforces Round #694 DIV1 E問題 (2000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20210103-1）のコード

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

//no-unlocked
int N, C, Q, A[3d4], X; ll Y;
ll cnt[5][3d4+2];
int sz, lis[5], ind[5];
int usz[3d4+2], ulis[3d4+2][5];
int dsz[3d4+2], dlis[3d4+2][5];
Arr1d<__int128_t> skip[5];
{
  int i, j, k, c;
  rep(i,5) cnt[i][0] = 1;
  rep(i,5) rep(k,3d4) rep(j,min(k,i)+1){
    cnt[i][k+1] += cnt[i-j][k-j];
    if(cnt[i][k+1] > 2d18) cnt[i][k+1] = 2d18;
  }
  REP(rd_int()){
    rd(N,C,Q,A(N));

    rep(k,N){
      sz = 0;
      rep(i,C+1) if(k+i < N) arrInsert(sz, sz, ind, i, lis, A[k+i]);
      sortA(sz, lis, ind);
      j = usz[k] = dsz[k] = 0;
      rep(i,sz){
        if(ind[i] == 0) j++, continue;
        if(j==0) ulis[k][usz[k]++] = ind[i];
        if(j==1) dlis[k][dsz[k]++] = ind[i];
      }
    }

    rep(c,C+1){
      skip[c].setN(N);
      rep(k,N){
        skip[c][k] = 0;
        rep(i,usz[k]) if(c >= ulis[k][i]) skip[c][k] += cnt[c-ulis[k][i]][N-k-ulis[k][i]-1];
      }
    }

    rep(Q){
      rd(X--, Y--);
      if(Y >= cnt[C][N]) wt(-1), continue;
      c = C;
      rep(k,N){
        i = bsearch_max[int,i,k-1,N-1](skip[c].getSum(k,i) <= Y < skip[c].getSum(k,i) + cnt[c][N-i-1])+ 1;
        if(X < i) wt(A[X]), break;
        Y -= skip[c].getSum(k, i-1);
        k = i;

        rep(i,usz[k]) if(c >= ulis[k][i]){
          if(Y < cnt[c-ulis[k][i]][N-k-ulis[k][i]-1]){
            if(X <= k + ulis[k][i]) wt(A[k+ulis[k][i]-(X-k)]), break_break;
            c -= ulis[k][i];
            k += ulis[k][i];
            break_continue;
          } else {
            Y -= cnt[c-ulis[k][i]][N-k-ulis[k][i]-1];
          }
        }
        if(Y < cnt[c][N-k-1]){
          if(X == k) wt(A[k]), break;
          continue;
        } else {
          Y -= cnt[c][N-k-1];
        }
        rep(i,dsz[k]) if(c >= dlis[k][i]){
          if(Y < cnt[c-dlis[k][i]][N-k-dlis[k][i]-1]){
            if(X <= k + dlis[k][i]) wt(A[k+dlis[k][i]-(X-k)]), break_break;
            c -= dlis[k][i];
            k += dlis[k][i];
            break_continue;
          } else {
            Y -= cnt[c-dlis[k][i]][N-k-dlis[k][i]-1];
          }
        }
      }
    }
  }
}

Current time: 2024年04月26日00時43分35秒
Last modified: 2021年01月08日22時28分10秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF694 CF_DIV1_E
トップページに戻る

Logged in as: unknown user (not login)