Submission #77092

#	Time	Username	Problem	Language	Result	Execution time	Memory
77092		shoemakerjo	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	72 ms	33984 KiB

molecules

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

#define ll long long
using namespace std;

#define pli pair<ll, int>

vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pli> vs;
    for (int i = 0; i < w.size(); i++) {
    	vs.push_back(pli(w[i], i));
    }
    sort(vs.begin(), vs.end());
    if (vs[0].first > u) return {};
    ll csum = 0LL;
    int start = 0;
    for (int i = 0; i < vs.size(); i++) {
    	if (csum + vs[i].first <= u) {
    		csum += vs[i].first;
    		if (csum >= l) {
    			vector<int> ans;
    			for (int j = start; j  <= i; j++) {
    				ans.push_back(vs[j].second);
    			}
    			return ans;
    		}
    		continue;
    	}
    	csum += vs[i].first;
    	csum -= vs[start++].first;
    	if (csum >= l) {
    		vector<int> ans;
    			for (int j = start; j  <= i; j++) {
    				ans.push_back(vs[j].second);
    			}
    			return ans;
    	}
    }



    return {};
    
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:11:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < w.size(); i++) {
                     ~~^~~~~~~~~~
molecules.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vs.size(); i++) {
                     ~~^~~~~~~~~~~

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