結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-18 22:46:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 1,728 bytes |
コンパイル時間 | 917 ms |
コンパイル使用メモリ | 88,492 KB |
最終ジャッジ日時 | 2025-01-07 23:22:20 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <iostream> #include <vector> #include <functional> using namespace std; typedef long long ll; int main(){ ll N,L,R; cin >> N >> L >> R; vector<ll> A(N); for(int i=0;i<N;i++) cin >> A[i]; vector<int> r(61,-1); bool ok = true; for(int i=0;i<N-1;i++){ for(int j=60;j>=0;j--){ if((A[i+1]&(1LL<<j)) && !(A[i]&(1LL<<j))){ if(r[j]==1) ok = false; r[j] = 0; break; } if(!(A[i+1]&(1LL<<j)) && (A[i]&(1LL<<j))){ if(r[j]==0) ok = false; r[j] = 1; break; } } } if(!ok){ cout << 0 << endl; return 0; } function<ll(ll)> calc = [&](ll x){ int h = 0; for(int j=0;j<61;j++){ if(x&(1LL<<j)) h = j; } for(int j=h+1;j<61;j++) if(r[j]==1) return 0LL; ll dp[70][2][2] = {}; dp[h+1][0][0] = 1; for(int i=h;i>=0;i--){ for(int nj=0;nj<2;nj++){ if(nj==0 && r[i]==1) continue; if(nj==1 && r[i]==0) continue; for(int j=0;j<2;j++){ for(int k=0;k<2;k++){ if(!(x&(1LL<<i)) && k==0 && nj==1) continue; int nk = 1; if(!(x&(1LL<<i)) && k==0 && nj==0) nk = 0; if((x&(1LL<<i)) && k==0 && nj==1) nk = 0; dp[i][nj][nk] += dp[i+1][j][k]; } } } } ll res = 0; for(int j=0;j<2;j++) for(int k=0;k<2;k++) res += dp[0][j][k]; return res; }; cout << calc(R)-(L!=0? calc(L-1):0) << endl; }