Submission #775602

#	Time	Username	Problem	Language	Result	Execution time	Memory
775602		Ludissey	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	37 ms	7144 KiB

molecules

#include "molecules.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>

using namespace std;
int l, u;
vector<pair<int, int>> w_sort;
vector<int> out;

std::vector<int> find_subset(signed _l, signed _u, std::vector<int> w) {
    l = _l;
    u = _u;
    int n = w.size();
    w_sort.resize(n);
    vector<long long> prefx(n + 1);
    for (int i = 0; i < n; i++) w_sort[i] = { w[i],i };
    sort(w_sort.begin(), w_sort.end());
    for (int i = 1; i <= n; i++)
    {
        prefx[i] = prefx[i - 1] + w_sort[i - 1].first;
    }
    int i = 0, j = 0;
    bool res=false;
    while (i <= j && j < n) {
        long long sum = prefx[j + 1] - prefx[i];
        if (sum >= l && sum <= u) {
            res = true;
            break;
        }
        else if (sum < l) {
            j++;
            if (j >= n) break;
        }
        else {
            if (i == j) j++;
            if (j >= n) break;
            i++;
        }
    }
    if (res) {
        for (int v = i; v <= j; v++) out.push_back(w_sort[v].second);
        return out;
    }
    return std::vector<int>(0);
}

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