Submission #422965

#	Time	Username	Problem	Language	Result	Execution time	Memory
422965		KienTranluvChaeng	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	204 KiB

molecules

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

using namespace std;

const int O = 2e5 + 1;

struct dou{
    int w, i;
};

bool how_sort(dou x, dou y){
    return x.w < y.w;
};

vector <int> find_subset(int l, int u, vector <int> w){
    int n = w.size();
    vector <dou> v(n);
    for (int i = 0; i < n; ++ i) v[i] = {w[i], i};

    vector <int> ans;
    deque <int> q;
    sort(v.begin(), v.end(), how_sort);
    int sum; sum = 0;
    for (int i = 0; i < n; ++ i){
        sum += v[i].w;
        if (sum > u){
            sum -= v[i].w;
            break;
        }
        q.push_back(i);
    }
    int rt = n - 1;
    while (sum < l && q.size() && rt > 0){
        sum -= v[q.front()].w;
        q.pop_front();
        sum += v[rt].w;
        q.push_back(rt);
        rt -= 1;
    }

    if (sum > u) return ans;

    while (q.size()){
        ans.push_back(v[q.back()].i);
        q.pop_back();
    }
    return ans;
}

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