daily pastebin goal
7%
SHARE
TWEET

Untitled

a guest Feb 24th, 2013 1,802 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <stack>
  7. #include <queue>
  8. #include <algorithm>
  9. #include <sstream>
  10. #include <iostream>
  11. #include <iomanip>
  12. #include <cstdio>
  13. #include <cmath>
  14. #include <cstdlib>
  15. #include <memory.h>
  16. #include <ctime>
  17.  
  18. using namespace std;
  19.  
  20. #define ABS(a) ((a>0)?a:-(a))
  21. #define MIN(a,b) ((a<b)?(a):(b))
  22. #define MAX(a,b) ((a<b)?(b):(a))
  23. #define FOR(i,a,n) for (int i=(a);i<(n);++i)
  24. #define FI(i,n) for (int i=0; i<(n); ++i)
  25. #define pnt pair <int, int>
  26. #define mp make_pair
  27. #define PI 3.14159265358979
  28. #define MEMS(a,b) memset(a,b,sizeof(a))
  29. #define LL long long
  30. #define U unsigned
  31.  
  32. LL solveStupid(LL l, LL r)
  33. {
  34.         LL res=0;
  35.         for (LL i=l; i<=r; ++i)
  36.                 for (LL j=i; j<=r; ++j)
  37.                         res=max(res,i^j);
  38.         return res;
  39. }
  40. string s1,s2;
  41. LL dp[70][2][2][2][2];
  42.  
  43. LL rec(int p, int fl1, int fl2, int fr1, int fr2)
  44. {
  45.         if (p==s1.size())
  46.                 return 0;
  47.         if (dp[p][fl1][fl2][fr1][fr2]!=-1)
  48.                 return dp[p][fl1][fl2][fr1][fr2];
  49.         int min1=0,max1=1;
  50.         if ((fl1==0) && (s1[p]=='1'))
  51.                 min1=1;
  52.         if ((fl2==0) && (s2[p]=='0'))
  53.                 max1=0;
  54.         int min2=0,max2=1;
  55.         if ((fr1==0) && (s1[p]=='1'))
  56.                 min2=1;
  57.         if ((fr2==0) && (s2[p]=='0'))
  58.                 max2=0;
  59.         LL res=0;
  60.         FOR(i,min1,max1+1)
  61.                 FOR(j,min2,max2+1)
  62.                 {
  63.                         int v=(i^j);
  64.                         LL toadd=0;
  65.                         if (v==1)
  66.                         {
  67.                                 int step=s1.size()-p-1;
  68.                                 toadd=(1ll<<step);
  69.                         }
  70.                         int nfl1=fl1,nfl2=fl2,nfr1=fr1,nfr2=fr2;
  71.                         if (i>s1[p]-'0')
  72.                                 nfl1=1;
  73.                         if (i<s2[p]-'0')
  74.                                 nfl2=1;
  75.                         if (j>s1[p]-'0')
  76.                                 nfr1=1;
  77.                         if (j<s2[p]-'0')
  78.                                 nfr2=1;
  79.                         res=max(res,toadd+rec(p+1,nfl1,nfl2,nfr1,nfr2));
  80.                 }
  81.         return dp[p][fl1][fl2][fr1][fr2]=res;
  82. }
  83. string getbin(LL num)
  84. {
  85.         string res="";
  86.         while (num)
  87.         {
  88.                 res+=((num&1)+'0');
  89.                 num/=2;
  90.         }
  91.         reverse(res.begin(),res.end());
  92.         return res;
  93. }
  94. LL solveSmart(LL l, LL r)
  95. {
  96.         s1=getbin(l);
  97.         s2=getbin(r);
  98.         while (s1.size()<s2.size())
  99.                 s1="0"+s1;
  100.         MEMS(dp,-1);
  101.         LL res=rec(0,0,0,0,0);
  102.         return res;
  103. }
  104. int main()
  105. {
  106. #ifdef Fcdkbear
  107.     freopen("in.txt","r",stdin);
  108.     //freopen("out.txt","w",stdout);
  109.     double beg=clock();
  110. #endif
  111.    LL l,r;
  112.    cin>>l>>r;
  113.    cout<<solveSmart(l,r)<<endl;
  114.  
  115. #ifdef Fcdkbear
  116.     double end=clock();
  117.     fprintf(stderr,"*** Total time = %.3lf ***\n",(end-beg)/CLOCKS_PER_SEC);
  118. #endif
  119.     return 0;
  120. }
RAW Paste Data
Top