Submission #138816

#	Time	Username	Problem	Language	Result	Execution time	Memory
138816		RiscadoA	Detecting Molecules (IOI16_molecules)	C++14	9 / 100	2 ms	376 KiB

molecules

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

const int MAX_N = 200000;

std::vector<int> find_subset(int l, int u, std::vector<int> wo)
{
        std::vector<int> ret;
        
        std::vector<std::pair<int, int>> w;
        for (int i = 0; i < (int)wo.size(); ++i)
                w.push_back(std::make_pair(wo[i], i));

        std::sort(w.begin(), w.end());
        int i, sum;
        for (i = 0, sum = 0; i < MAX_N; ++i) {
                sum += w[i].first;
                if (sum >= l) {
                        ++i;
                        break;
                }
        }
        if (sum < l)
                return {};
        else if (sum <= u)
                for (int j = 0; j < i; ++j)
                        ret.push_back(w[j].second);
        else {
                int j;
                for (j = 0; j < i; ++j) {
                        sum -= w[j].first;
                        if (sum <= u) {
                                ++j;
                                break;
                        }
                }
                
                if (sum < l)
                        return {};
                for (; j < i; ++j)
                        ret.push_back(w[j].second);

        }
        return ret;
}

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