結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2020-03-28 15:19:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 2,492 bytes |
コンパイル時間 | 1,760 ms |
コンパイル使用メモリ | 163,984 KB |
実行使用メモリ | 52,048 KB |
最終ジャッジ日時 | 2025-01-02 11:26:32 |
合計ジャッジ時間 | 8,906 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define ALL(x) x.begin(),x.end()#define rep(i,n) for(int i=0;i<(n);i++)#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define INF 1000000000#define mod 1000000007using ll=long long;const ll LINF=1001002003004005006ll;int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}ll n,lw,hi,vmin;vector<int> v(62,-1);int a[200001][62];bool match=true;bool fill(int l,int r,int d){if(d<0) return true;int ch=0;for(int i=l;i<r;i++){if(a[i][d]!=a[i+1][d]) ch++;}if(ch>=2) return false;if(ch==1){int res=a[l][d];if(v[d]<0) v[d]=res;else{if(res!=v[d]) match=false;}}int mid;for(mid=l;mid<=r and a[l][d]==a[mid][d];mid++){}bool ret=true;if(!fill(l,mid-1,d-1)){ret=false;}if(mid<=r){if(!fill(mid,r,d-1)){ret=false;}}return ret;}ll ketaDP(ll mn){if(mn<=0) return 0;ll m[62]={};rep(i,62)m[i]=((mn>>i)&1);ll dp[63][2][2]={};dp[62][0][0]=1;for(int i=61;i>=0;i--){if(v[i]<0){//ギリギリfor(int k=0;k<=m[i];k++){dp[i][(k<m[i])][k]+=dp[i+1][0][0]+dp[i+1][0][1];}rep(k,2){dp[i][1][k]+=dp[i+1][1][0]+dp[i+1][1][1];}}else{dp[i][1][v[i]]+=dp[i+1][1][0]+dp[i+1][1][1];if(m[i]>=v[i]) dp[i][m[i]>v[i]][v[i]]+=dp[i+1][0][0]+dp[i+1][0][1];}}// cout<<mn<<endl;// cout<<" ";// for(int i=62;i>=0;i--){// cout<<m[i]<<" ";// }cout<<endl;// rep(j,2){// rep(k,2){// cout<<j<<" "<<k<<" : ";// for(int i=62;i>=0;i--){// cout<<dp[i][j][k]<<" ";// }cout<<endl;// }// }return dp[0][1][0]+dp[0][0][0]+dp[0][1][1]+dp[0][0][1];}signed main(){cin.tie(0);ios::sync_with_stdio(0);cin>>n>>lw>>hi;rep(i,n){ll t;cin>>t;rep(j,62){a[i][j]=(t>>j)&1;}}if(!fill(0,n-1,61) or !match){cout<<0<<endl;return 0;}// debug(v);cout<<ketaDP(hi)-ketaDP(lw-1)<<endl;return 0;}