Codeforces Round #562 DIV1 C問題/DIV2 E問題 - And Reachability

Source

Codeforces Round #562 DIV1 C問題 (1500pt)
Codeforces Round #562 DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略
以下のコードは想定解法より遅くメモリ使用量も多い.

cLayversion 20190526-1)のコード

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

//no-unlocked

int N, Q, A[3d5];

int nx[171][3d5];
int cnv[19][19];

{
  int i, j, k, mask;
  int x, y, z, s, ok;

  rd(N,Q,A(N));

  k = 0;
  rep(i,19) REP(j,i+1,19) cnv[i][j] = cnv[j][i] = k++;

  rep(i,19) rep(j,i+1,19){
    mask = ((1<<i) | (1<<j));
    k = cnv[i][j];
    nx[k][N-1] = N;
    for(x=N-2;x>=0;x--){
      nx[k][x] = nx[k][x+1];
      if( (mask & A[x+1])==mask ) nx[k][x] = x+1;
    }
  }

  rep(Q){
    rd(x,y);
    x--; y--;
    z = A[x];

    ok = 0;
    while(x <= y){
      if(z & A[y]){ok = 1; break;}
      s = N;
      rep(i,19) if(z & 1<<i) rep(j,19) if(!(z & 1<<j)){
        s <?= nx[cnv[i][j]][x];
      }
      x = s;
      z |= A[x];
    }

    if(ok) wt("Shi"); else wt("Fou");
  }
}

Current time: 2021年09月17日16時03分42秒
Last modified: 2019年05月27日22時03分50秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF562 CF_Div1_C CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: