Submission #430482

#	Time	Username	Problem	Language	Result	Execution time	Memory
430482		Mamedov	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	66 ms	7104 KiB

molecules

#include "molecules.h"
#include <memory.h>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#define maxx 200005

using namespace std;

typedef long long ll;
struct data{
    ll w;
    int idx;
};
data p[maxx];

bool cmp(data a, data b){
    return a.w < b.w;
}


std::vector<int> find_subset(int l, int u, std::vector<int> weight){
    vector<int>res;
    res.clear();
    int n = weight.size();
    for(int i = 0; i < n; i++){
        p[i].w = 1LL * weight[i];
        p[i].idx = i;
    }
    sort(p, p + n, cmp);

    ll sum = 0;
    int ptr1 = 0, ptr2 = 0;
    while(ptr1 < n){
        while(ptr2 < n && sum < 1LL * l){
            sum += p[ptr2].w;
            ptr2++;
        }
        if(sum >= 1LL * l && sum <= 1LL * u){
            for(int i = ptr1; i < ptr2; i++){
                res.push_back(p[i].idx);
            }
            return res;
        }
        else{
            while(ptr1 < n && sum > 1LL * u){
                sum -= p[ptr1].w;
                ptr1++;
            }
        }
        if(ptr2 == n && sum < 1LL * l)
            break;
    }
    return res;
}

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