結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-19 13:14:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 1,870 bytes |
コンパイル時間 | 1,664 ms |
コンパイル使用メモリ | 171,120 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 01:56:30 |
合計ジャッジ時間 | 8,618 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
·#include"bits/stdc++.h"#define int long long#define _overload3(_1,_2,_3,name,...) name#define _rep(i,n) repi(i,0,n)#define repi(i,a,b) for(int i=(a);i<(b);++i)#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)#define All(x) (x).begin(),(x).end()#define rAll(x) (x).rbegin(),(x).rend()using namespace std;typedef pair<int,int> P;typedef vector<int> vi;typedef vector<vi> vvi;const int mod=1000000007;int gcd(int x,int y){return y?gcd(y,x%y):x;}int lcm(int x,int y){return x*y/gcd(x,y);}int roundup(int a,int b){return (a-1)/b+1;}signed main(){int N,L,R;cin>>N>>L>>R;vector<int> A(N);rep(i,N) cin>>A[i];int dig[62];rep(i,62) dig[i]=2;auto dic=[&](auto &&f,int l,int r,int bit)->bool{if(l==r) return true;if(bit==-1) return false;int flag=0,m=l;rep(i,l,r){if((A[i]>>bit&1)!=(A[i+1]>>bit&1)){flag++;m=i;}}if(flag>=2) return false;if(flag==1){if(A[l]>>bit&1){if(dig[bit]!=0) dig[bit]=1;else return false;}else{if(dig[bit]!=1) dig[bit]=0;else return false;}return f(f,l,m,bit-1)&&f(f,m+1,r,bit-1);}return f(f,l,r,bit-1);};if(!dic(dic,0,N-1,61)){cout<<0<<endl;return 0;}//rep(i,62) cout<<dig[i]<<" \n"[i==61];auto ans=[&](int U){if(U==-1) return 0LL;int dp[63][2]={};dp[62][1]=1;for(int i=61;i>=0;--i){dp[i][0]=dp[i+1][0];if(dig[i]==2){if(U>>i&1){dp[i][0]=2*dp[i+1][0]+dp[i+1][1];dp[i][1]=dp[i+1][1];}else{dp[i][0]=2*dp[i+1][0];dp[i][1]=dp[i+1][1];}}if(dig[i]==1){if(U>>i&1){dp[i][1]=dp[i+1][1];}}if(dig[i]==0){if(U>>i&1){dp[i][0]+=dp[i+1][1];}else{dp[i][1]=dp[i+1][1];}}}return dp[0][0]+dp[0][1];};cout<<ans(R)-ans(L-1)<<endl;}