Submission #360174

#	Time	Username	Problem	Language	Result	Execution time	Memory
360174		jesus_coconut	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	71 ms	5612 KiB

molecules

#include "molecules.h"
#include <algorithm>
using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pair<int, int>> v(w.size());
    for (int i = 0; i < (int) w.size(); ++i) {
    	v[i] = {w[i], i};
    }
    int n = w.size();
    sort(begin(v), end(v));
    int pl = 0, pr = 0;
    using ll = long long;
    ll suma = 0;
    while (suma < l || suma > u) {
    	bool bk = true;
    	while (suma < l && pr < n) {
    		suma += v[pr++].first;
    		bk = false;
    	}
    	while (suma > u && pl < pr) {
    		suma -= v[pl++].first;
    		bk = false;
    	}
    	if (bk) break;
    }
    if (suma < l || suma > u) return {};
    vector<int> ret;
    for (int i = pl; i < pr; ++i) {
    	ret.push_back(v[i].second);
    }
    return ret;
}

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