Submission #596935

#	Time	Username	Problem	Language	Result	Execution time	Memory
596935		jophyyjh	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	39 ms	5676 KiB

molecules

/**
 * If we've got a subset S and two elements x, y (not in S). We must not have:
 *                  sum(S + {x}) > u, sum(S + {y}) < v,
 * As this immediately violates the given constraint. We now can propose a solution.
 * 
 * Time Complexity: O(n * log(n))
 * Implementation 1
*/

#include <bits/stdc++.h>
#include "molecules.h"


struct val_t {
    int pos, val;
};

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    int n = w.size();
    std::vector<val_t> values(n);
    for (int k = 0; k < n; k++)
        values[k].val = w[k], values[k].pos = k;
    std::sort(values.begin(), values.end(),
              [](const val_t& v1, const val_t& v2) {
                 return v1.val < v2.val;
              });
    std::vector<int> prefix_sum(n + 1);
    prefix_sum[0] = 0;
    for (int i = 0; i < n; i++)
        prefix_sum[i + 1] = prefix_sum[i] + values[i].val;
    
    bool found = false;
    std::vector<int> ans;
    for (int i = n; i >= 1 && !found; i--) {
        int j = i;
        for (int step = n / 2 + 1; step >= 1; step /= 2) {
            while (j - step >= 0 && prefix_sum[i] - prefix_sum[j - step] <= u)
                j -= step;
        }
        if (prefix_sum[i] - prefix_sum[j] >= l) {
            assert(prefix_sum[i] - prefix_sum[j] <= u);
            found = true;
            for (int k = j; k < i; k++)
                ans.emplace_back(k);
        } else if (j > 0) {
            if (values[0].val + prefix_sum[i] - prefix_sum[j] <= u) {
                found = true;
                ans.emplace_back(0);
                for (int k = j; k < i; k++)
                    ans.emplace_back(k);
            }
        }
    }
    if (found) {    // test-driven development
        int sum = 0;
        for (int& a : ans) {
            sum += values[a].val;
            a = values[a].pos;
        }
        assert(sum >= l && sum <= u);
        return ans;
    } else {
        return std::vector<int>();
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31