Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- final class Task {
- public static InputReader in;
- public static OutputWriter out;
- public static DebugWriter dout;
- public void solve() {
- int n = in.readInt();
- long left = in.readLong();
- long right = in.readLong();
- long[] weight = new long[n];
- long[] value = new long[n];
- for (int i = 0; i < n; ++i) {
- weight[i] = in.readLong();
- value[i] = in.readLong();
- }
- if (n == 1) {
- if (left <= weight[0] && weight[0] <= right) {
- out.printLine(1);
- out.printLine(1);
- } else {
- out.printLine(0);
- }
- return;
- }
- int n1 = n / 2;
- int n2 = n - n1;
- TreeSet<Long> set = new TreeSet<>();
- set.add(0L);
- set.add(left);
- set.add(right);
- long[] leftValue = new long[1 << n1];
- long[] leftWeight = new long[1 << n1];
- for (int k = 0; k < (1 << n1); ++k) {
- long w = 0;
- long v = 0;
- for (int i = 0; i < n1; ++i)
- if (((k >> i) & 1) == 1) {
- w += weight[i];
- v += value[i];
- }
- leftValue[k] = v;
- leftWeight[k] = w;
- set.add(w);
- set.add(Math.max(0, left - w));
- set.add(Math.max(0, right - w));
- }
- maskValue = new long[1 << n2];
- long[] maskWeight = new long[1 << n2];
- for (int k = 0; k < (1 << n2); ++k) {
- long w = 0;
- long v = 0;
- for (int i = 0; i < n2; ++i)
- if (((k >> i) & 1) == 1) {
- w += weight[n1 + i];
- v += value[n1 + i];
- }
- maskValue[k] = v;
- maskWeight[k] = w;
- set.add(w);
- set.add(Math.max(0, left - w));
- set.add(Math.max(0, right - w));
- }
- TreeMap<Long, Integer> map = new TreeMap<>();
- int id = 0;
- for (long x : set)
- map.put(x, id++);
- init(id);
- for (int i = 0; i < (1 << n2); ++i) {
- // dout.printLine("w = " + maskWeight[i] + ", v = " + maskValue[i] + ", m = " + Integer.toBinaryString(i));
- put(map.get(maskWeight[i]), i);
- }
- // dout.printLine("map: " + map);
- // dout.printLine("tree: ");
- // id = 1;
- // for (int k = 1; id < 2 * size - 1; k *= 2) {
- // for (int i = 0; i < k; ++i)
- // out.print(tree[id++] + " ");
- // out.printLine();
- // }
- long bestMask = 0;
- long bestValue = 0;
- // dout.printLine(leftWeight);
- for (int k = 0; k < (1 << n1); ++k) {
- int q = get(map.get(Math.max(0, left - leftWeight[k])),
- map.get(Math.max(0, right - leftWeight[k])));
- // dout.printLine("queries");
- // dout.printLine(Math.max(0, left - leftWeight[k]) + " " +
- // Math.max(0, right - leftWeight[k]) + " " + q);
- long v = leftValue[k] + maskValue[q];
- long w = leftWeight[k] + maskWeight[q];
- if (left <= w && w <= right && bestValue < v) {
- bestValue = v;
- bestMask = ((long) k | ((long) q << n1));
- // dout.printLine(bestMask);
- }
- }
- // dout.printLine(bestMask);
- int count = 0;
- for (int i = 0; i < n; ++i)
- if (((bestMask >>> i) & 1) == 1) {
- // dout.printLine(i);
- ++count;
- }
- if (count == 0) {
- out.printLine(0);
- } else {
- out.printLine(count);
- for (int i = 0; i < n; ++i)
- if (((bestMask >>> i) & 1) == 1) {
- out.print(i + 1);
- --count;
- if (count == 0) out.printLine();
- else out.print(" ");
- }
- }
- }
- long maskValue[];
- int[] tree;
- int size;
- void init(int n) {
- size = 1;
- while (size < n)
- size *= 2;
- tree = new int[size * 2];
- }
- void put(int id, int mask) {
- id += size;
- if (maskValue[tree[id]] < maskValue[mask])
- tree[id] = mask;
- while (id > 1) {
- id /= 2;
- if (maskValue[tree[id * 2]] > maskValue[tree[id * 2 + 1]]) {
- tree[id] = tree[id * 2];
- } else {
- tree[id] = tree[id * 2 + 1];
- }
- }
- }
- int get(int left, int right) {
- left += size;
- right += size;
- int res = 0;
- for (; left <= right; left = (left + 1) / 2, right = (right - 1) / 2) {
- if ((left & 1) == 1 && maskValue[res] < maskValue[tree[left]]) {
- res = tree[left];
- }
- if ((right & 1) == 0 && maskValue[res] < maskValue[tree[right]]) {
- res = tree[right];
- }
- }
- return res;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement