結果
問題 |
No.822 Bitwise AND
|
ユーザー |
![]() |
提出日時 | 2019-04-27 00:11:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 752 ms / 2,000 ms |
コード長 | 1,462 bytes |
コンパイル時間 | 1,932 ms |
コンパイル使用メモリ | 169,972 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-25 18:16:33 |
合計ジャッジ時間 | 4,438 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0;i<((int)(n));i++) #define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++) #define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--) #define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--) typedef long long ll; /* N=0のとき、k>0ならいくらでもある。 */ ll n,k,ans=0; vector<int> v; void init(){ cin>>n>>k; rep(i,21)if(!(n & 1LL<<i))v.push_back(i);//空いてる場所 } int main(void){ init(); if(n<k){ ans=-1; }else{ rep(s,1<<v.size()){//置き方。 //w:既にxに1が入ってる場所 ll w[21]={},x=0; rep(i,21)if((n & 1LL<<i))w[i]=1; rep(i,v.size())if((s & 1LL<<i)){ w[v[i]]=1; x+=1<<v[i]; } vector<int> y;//yが使える場所 rep(i,21)if(w[i]==0 && 1LL<<i <= k+x)y.push_back(i); //ここも総当たりしなくても分かる ll tmp=k+x,sum1=1,sum2=0; irep(i,y.size()){ if(tmp>=(1LL<<y[i])){ sum1+=1LL<<i;//先頭を0にすればいい。 tmp-=1LL<<y[i];//先頭を1にした結果。 } } tmp=x-1; if(tmp>=0)sum2=1; irep(i,y.size()){ if(tmp>=(1LL<<y[i])){ sum2+=1LL<<i;//先頭を0にすればいい。 tmp-=1LL<<y[i];//先頭を1にした結果。 } } ans+=sum1-sum2; // if(sum1-sum2>0)printf("%lld,%lld,%lld\n",sum1,sum2,x); if(x>1000000 && sum1-sum2>0)ans=-1e18; } } if(ans<0){ cout<<"INF"<<endl; }else{ cout<<ans<<endl; } return 0; }