Advertisement
Guest User

Untitled

a guest
Nov 1st, 2014
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.03 KB | None | 0 0
  1. final class Task {
  2.     public static InputReader in;
  3.     public static OutputWriter out;
  4.     public static DebugWriter dout;
  5.    
  6.     public void solve() {
  7.         int n = in.readInt();
  8.         long left = in.readLong();
  9.         long right = in.readLong();
  10.        
  11.         long[] weight = new long[n];
  12.         long[] value = new long[n];
  13.        
  14.         for (int i = 0; i < n; ++i) {
  15.             weight[i] = in.readLong();
  16.             value[i] = in.readLong();
  17.         }
  18.        
  19.         if (n == 1) {
  20.             if (left <= weight[0] && weight[0] <= right) {
  21.                 out.printLine(1);
  22.                 out.printLine(1);
  23.             } else {
  24.                 out.printLine(0);
  25.             }
  26.             return;
  27.         }
  28.        
  29.         int n1 = n / 2;
  30.         int n2 = n - n1;
  31.        
  32.         TreeSet<Long> set = new TreeSet<>();
  33.         set.add(0L);
  34.         set.add(left);
  35.         set.add(right);
  36.        
  37.         long[] leftValue = new long[1 << n1];
  38.         long[] leftWeight = new long[1 << n1];
  39.         for (int k = 0; k < (1 << n1); ++k) {
  40.             long w = 0;
  41.             long v = 0;
  42.             for (int i = 0; i < n1; ++i)
  43.                 if (((k >> i) & 1) == 1) {
  44.                     w += weight[i];
  45.                     v += value[i];
  46.                 }
  47.                
  48.             leftValue[k] = v;
  49.             leftWeight[k] = w;
  50.             set.add(w);
  51.             set.add(Math.max(0, left - w));
  52.             set.add(Math.max(0, right - w));
  53.         }
  54.        
  55.         maskValue = new long[1 << n2];
  56.         long[] maskWeight = new long[1 << n2];
  57.        
  58.         for (int k = 0; k < (1 << n2); ++k) {
  59.             long w = 0;
  60.             long v = 0;
  61.             for (int i = 0; i < n2; ++i)
  62.                 if (((k >> i) & 1) == 1) {
  63.                     w += weight[n1 + i];
  64.                     v += value[n1 + i];
  65.                 }
  66.             maskValue[k] = v;
  67.             maskWeight[k] = w;
  68.             set.add(w);
  69.             set.add(Math.max(0, left - w));
  70.             set.add(Math.max(0, right - w));
  71.         }
  72.        
  73.         TreeMap<Long, Integer> map = new TreeMap<>();
  74.         int id = 0;
  75.         for (long x : set)
  76.             map.put(x, id++);
  77.        
  78.         init(id);
  79.         for (int i = 0; i < (1 << n2); ++i) {
  80.             // dout.printLine("w = " + maskWeight[i] + ", v = " + maskValue[i] + ", m = " + Integer.toBinaryString(i));
  81.             put(map.get(maskWeight[i]), i);    
  82.         }
  83.        
  84.         // dout.printLine("map: " + map);
  85.         // dout.printLine("tree: ");
  86.         // id = 1;
  87.         // for (int k = 1; id < 2 * size - 1; k *= 2) {
  88.         //  for (int i = 0; i < k; ++i)
  89.         //      out.print(tree[id++] + " ");
  90.         //  out.printLine();
  91.         // }
  92.        
  93.         long bestMask = 0;
  94.         long bestValue = 0;
  95.        
  96.         // dout.printLine(leftWeight);
  97.        
  98.         for (int k = 0; k < (1 << n1); ++k) {
  99.             int q = get(map.get(Math.max(0, left - leftWeight[k])),
  100.                 map.get(Math.max(0, right - leftWeight[k])));
  101.            
  102.             // dout.printLine("queries");
  103.             // dout.printLine(Math.max(0, left - leftWeight[k]) + " " +
  104.                 // Math.max(0, right - leftWeight[k]) + " " + q);
  105.            
  106.             long v = leftValue[k] + maskValue[q];
  107.             long w = leftWeight[k] + maskWeight[q];
  108.            
  109.             if (left <= w && w <= right && bestValue < v) {
  110.                 bestValue = v;
  111.                 bestMask = ((long) k | ((long) q << n1));
  112.                 // dout.printLine(bestMask);
  113.             }          
  114.         }
  115.        
  116.         // dout.printLine(bestMask);
  117.        
  118.         int count = 0;
  119.         for (int i = 0; i < n; ++i)
  120.             if (((bestMask >>> i) & 1) == 1) {
  121.                 // dout.printLine(i);
  122.                 ++count;
  123.             }
  124.            
  125.         if (count == 0) {
  126.             out.printLine(0);
  127.         } else {
  128.             out.printLine(count);
  129.             for (int i = 0; i < n; ++i)
  130.                 if (((bestMask >>> i) & 1) == 1) {
  131.                     out.print(i + 1);
  132.                     --count;
  133.                     if (count == 0) out.printLine();
  134.                     else out.print(" ");
  135.                 }
  136.         }
  137.    
  138.        
  139.     }
  140.    
  141.    
  142.     long maskValue[];
  143.    
  144.     int[] tree;
  145.     int size;
  146.    
  147.     void init(int n) {
  148.         size = 1;
  149.         while (size < n)
  150.             size *= 2;
  151.        
  152.         tree = new int[size * 2];
  153.     }
  154.    
  155.     void put(int id, int mask) {
  156.         id += size;
  157.         if (maskValue[tree[id]] < maskValue[mask])
  158.             tree[id] = mask;
  159.        
  160.         while (id > 1) {
  161.             id /= 2;
  162.             if (maskValue[tree[id * 2]] > maskValue[tree[id * 2 + 1]]) {
  163.                 tree[id] = tree[id * 2];
  164.             } else {
  165.                 tree[id] = tree[id * 2 + 1];
  166.             }
  167.         }
  168.     }
  169.    
  170.     int get(int left, int right) {
  171.         left += size;
  172.         right += size;
  173.        
  174.         int res = 0;
  175.        
  176.         for (; left <= right; left = (left + 1) / 2, right = (right - 1) / 2) {
  177.             if ((left & 1) == 1 && maskValue[res] < maskValue[tree[left]]) {
  178.                 res = tree[left];
  179.             }
  180.            
  181.             if ((right & 1) == 0 && maskValue[res] < maskValue[tree[right]]) {
  182.                 res = tree[right];
  183.             }
  184.         }
  185.        
  186.         return res;
  187.     }
  188. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement