Advertisement
Guest User

Untitled

a guest
Feb 24th, 2013
5,715
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement