daily pastebin goal
7%
SHARE
TWEET

Untitled

a guest Feb 24th, 2013 183 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
Top