Submission #900098

#	Time	Username	Problem	Language	Result	Execution time	Memory
900098		mannshah1211	Detecting Molecules (IOI16_molecules)	C++14	9 / 100	1 ms	348 KiB

molecules

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

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    std::vector<std::pair<int, int>> indices;
    for (int i = 0; i < w.size(); i++) {
    	indices.push_back(std::make_pair(w[i], i));
    }
    int n = indices.size();
    std::vector<int> prefix_sums(n);
    for (int i = 0; i < n; i++) {
    	if (i == 0) {
    		prefix_sums[i] = indices[i].first;
    	} else {
    		prefix_sums[i] = prefix_sums[i - 1] + indices[i].first;
    	}
    }
    std::function<int(int, int)> segment_sum = [&](int l, int r) {
    	if (l == 0) {
    		return prefix_sums[r];
    	} else {
    		return prefix_sums[r] - prefix_sums[l - 1];
    	}
    };
    std::sort(indices.begin(), indices.end());
    for (int i = 0; i < n; i++) {
    	int low = i, high = n - 1, index = -1;
    	while (low <= high) {
    		int middle = (low + high) / 2;
    		if (segment_sum(i, middle) >= l) {
    			index = middle;
    			high = middle - 1;
    		} else {
    			low = middle + 1;
    		}
    	}
    	if (index != -1) {
    		assert(segment_sum(i, index) >= l);
    	}
    	if (index != -1 && segment_sum(i, index) <= u) {
    		std::vector<int> answer;
    		for (int j = i; j <= index; j++) {
    			answer.push_back(indices[j].second);
    		}
    		return answer;
    	}
    }
    return {};
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (int i = 0; i < w.size(); i++) {
      |                     ~~^~~~~~~~~~

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