Submission #742564

#	Time	Username	Problem	Language	Result	Execution time	Memory
742564		oyber	Detecting Molecules (IOI16_molecules)	C++14	9 / 100	1 ms	292 KiB

molecules

#include "molecules.h"
#include <algorithm>
#include <utility>

using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = int(w.size());
    vector<pair<int, int>> ws;
    for (int i = 0; i < n; i++) {
        ws.push_back(make_pair(w[i], i));
    }
    sort(ws.begin(), ws.end());
    int a = ws[0].first;
    vector<int> s1(n+1);
    vector<int> s2(n+1);
    for (int i = 0; i < n; i++) {
        ws[i].first -= a;
        s1[i+1] = s1[i]+ws[i].first;
    }

    for (int i = 0; i < n; i++) {
        s2[i+1] = s2[i]+ws[n-i-1].first;
    }

    for (int i = 0; i <= n; i++) {
        //printf("%d %d, %d %d\n", l, u, s1[i], s2[i]);
        if (s1[i] >= l && s1[i] <= u) {
            vector<int> result;
            for (int j = 0; j < i; j++) {
                result.push_back(ws[j].second);
            }
            return result;
        }
        if (s2[i] >= l && s2[i] <= u) {
            vector<int> result;
            for (int j = n-1; j >= n-i; j--) {
                result.push_back(ws[j].second);
            }
            return result;
        }

        l -= a;
        u -= a;
    }

    return vector<int>(0);
}

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