Submission #597635

#	Time	Username	Problem	Language	Result	Execution time	Memory
597635		jophyyjh	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	53 ms	7116 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. I proposed the following way
 * of selecting numbers. Take S as the empty set, sort the numbers from large to
 * small and consider them iteratively. If adding the current num to S keeps
 * sum(S) <= u, we add it. I noticed that if the selected numbers don't form a
 * consecutive segment, then there exists two numbers x > y where x isn't picked
 * while y is. This case is solved. In other words, i just have to go through each
 * position i and consider the maximal subarray ending at i. By induction i also
 * proved that this is sufficient and necessary.
 * 
 * Thomas and the editorial both provided simpler solutions. Instead of "adding
 * numbers", we try "switching numbers", which better suits the property. The
 * general idea is to iterate through all k, the size of our subset. For each k,
 * if #sum_of_smallest_k_num >= l or #sum_of_greatest_k_num <= u the situation is
 * easy to consider. When #sum_of_smallest_k_num < l and
 * #sum_of_greatest_k_num > u, we can "smoothly" change our subset, eg by taking
 * all subarrays of len k (on our sorted list). Shifting the frame right by 1 means
 * to delete a num and add another one.
 * 
 * Time Complexity: O(n * log(n))
 * Implementation 1
*/
 
#include <bits/stdc++.h>
#include "molecules.h"
 
typedef long long   ll;
 
 
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<ll> 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] <= ll(u))
                j -= step;
        }
        if (prefix_sum[i] - prefix_sum[j] >= ll(l)) {
            assert(prefix_sum[i] - prefix_sum[j] <= ll(u));
            found = true;
            for (int k = j; k < i; k++)
                ans.emplace_back(k);
        } else if (j > 0) {
            if (ll(values[0].val) + prefix_sum[i] - prefix_sum[j] <= ll(u)) {
                found = true;
                ans.emplace_back(0);
                for (int k = j; k < i; k++)
                    ans.emplace_back(k);
            }
        }
    }
    if (found) {    // test-driven development
        ll sum = 0;
        for (int& a : ans) {
            sum += values[a].val;
            a = values[a].pos;
        }
        assert(sum >= ll(l) && sum <= ll(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: 31 / 31