Advertisement
Guest User

Untitled

a guest
Feb 24th, 2013
873
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.56 KB | None | 0 0
  1. /**
  2.  * Created with IntelliJ IDEA.
  3.  * User: Fcdkbear
  4.  * Date: 11.02.13
  5.  * Time: 16:48
  6.  * To change this template use File | Settings | File Templates.
  7.  */
  8. import java.util.Scanner;
  9.  
  10. public class test {
  11.     static long[][][][][] dp;
  12.     static String s1,s2;
  13.     static String getbin (long num)
  14.     {
  15.         String tmp="";
  16.         while (num>0)
  17.         {
  18.             long v=(num%2);
  19.             tmp+=(char)(v+'0');
  20.             num/=2;
  21.         }
  22.         String res="";
  23.         int n=tmp.length();
  24.         for (int i=n-1; i>=0; --i)
  25.             res+=tmp.charAt(i);
  26.         return res;
  27.     }
  28.     static int len;
  29.     static long rec(int p, int fl1, int fl2, int fr1, int fr2)
  30.     {
  31.         if (p==len)
  32.             return 0;
  33.         if (dp[p][fl1][fl2][fr1][fr2] != -1)
  34.             return dp[p][fl1][fl2][fr1][fr2];
  35.         int min1 = 0, max1 = 1;
  36.         if ((fl1 == 0) && (s1.charAt(p) == '1'))
  37.             min1 = 1;
  38.         if ((fl2 == 0) && (s2.charAt(p) == '0'))
  39.             max1 = 0;
  40.         int min2 = 0, max2 = 1;
  41.         if ((fr1 == 0) && (s1.charAt(p) == '1'))
  42.             min2 = 1;
  43.         if ((fr2 == 0) && (s2.charAt(p) == '0'))
  44.             max2 = 0;
  45.         long res = 0;
  46.         for (int i=min1; i<=max1; ++i)
  47.         for (int j=min2; j<=max2; ++j)
  48.         {
  49.             int v = (i ^ j);
  50.             long toadd = 0;
  51.             if (v == 1) {
  52.                 int step = len - p - 1;
  53.                 toadd = (1L << step);
  54.             }
  55.             int nfl1 = fl1, nfl2 = fl2, nfr1 = fr1, nfr2 = fr2;
  56.             if (i > s1.charAt(p) - '0')
  57.                 nfl1 = 1;
  58.             if (i < s2.charAt(p) - '0')
  59.                 nfl2 = 1;
  60.             if (j > s1.charAt(p) - '0')
  61.                 nfr1 = 1;
  62.             if (j < s2.charAt(p) - '0')
  63.                 nfr2 = 1;
  64.             long res1= toadd + rec(p + 1, nfl1, nfl2, nfr1, nfr2);
  65.             res = Math.max(res,res1);
  66.         }
  67.         return dp[p][fl1][fl2][fr1][fr2] = res;
  68.     }
  69.     public static void main(String [] args)
  70.     {
  71.         dp=new long[70][2][2][2][2];
  72.         for (int i=0; i<70; ++i)
  73.             dp[i]=new long[2][2][2][2];
  74.         for (int i = 0; i < 70; ++i)
  75.             for (int j=0; j<2; ++j)
  76.                 dp[i][j] = new long[2][2][2];
  77.         for (int i = 0; i < 70; ++i)
  78.             for (int j = 0; j < 2; ++j)
  79.                 for (int k=0; k<2; ++k)
  80.                     dp[i][j][k] = new long[2][2];
  81.         for (int i = 0; i < 70; ++i)
  82.             for (int j = 0; j < 2; ++j)
  83.                 for (int k = 0; k < 2; ++k)
  84.                     for (int c=0; c<2; ++c)
  85.                         dp[i][j][k][c] = new long[2];
  86.         for (int i = 0; i < 70; ++i)
  87.             for (int j = 0; j < 2; ++j)
  88.                 for (int k = 0; k < 2; ++k)
  89.                     for (int c = 0; c < 2; ++c)
  90.                         for (int l=0; l<2; ++l)
  91.                             dp[i][j][k][c][l]=-1;
  92.         Scanner sc = new Scanner(System.in);
  93.         long l=sc.nextLong();
  94.         long r=sc.nextLong();
  95.         s1=getbin(l);
  96.         s2=getbin(r);
  97.         while (s1.length()<s2.length())
  98.             s1="0"+s1;
  99.         len=s1.length();
  100.         //System.out.println(s1);
  101.         //System.out.println(s2);
  102.         long res=rec(0,0,0,0,0);
  103.         System.out.println(res);
  104.     }
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement