Submission #869888

#	Time	Username	Problem	Language	Result	Execution time	Memory
869888		Matjaz	Detecting Molecules (IOI16_molecules)	C++14	31 / 100	1077 ms	616 KiB

molecules

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

using namespace std;

vector<long long> s;
long long total;
int N;
vector<pair<int,int> > tmp;
int l,u;
vector<int> w;

long long sum(int small, int big){
    return s[small] + total - s[N - big];
}

vector<int> output_vector(int small, int big, int position){
    vector<int> v;
    
    for (int i=0;i<small;i++) v.push_back(tmp[i].second);
    
    if (position != -1) v.push_back(tmp[position].second);
    
    for (int i=N-big;i<N;i++) v.push_back(tmp[i].second);
    
    return v;
}

bool works(int small, int big, int position){
    
    long long weight = sum(small, big) + (position != -1 ? w[position] : 0);
    
    //printf("%d %d %d: %lld\n", small, big, position, weight);
    
    if (l <= weight && weight <= u) return true;
    
    return false;
}



std::vector<int> find_subset(int _l, int _u, std::vector<int> _w) {
    l = _l;
    u = _u;
    w = _w;
    total = 0;
    N = w.size();
    for (int i=0;i<N;i++) total += w[i];
    
    tmp.assign(N, make_pair(-1,-1));
    for (int i=0;i<N;i++){
        tmp[i].first = w[i];
        tmp[i].second = i;
    }
    sort(tmp.begin(), tmp.end());
    for (int i=0;i<N;i++) w[i] = tmp[i].first;
    
    s.assign(N + 1, 0);
    s[0] = 0;
    for(int i=0;i<N;i++) s[i + 1] = s[i] + w[i];

    for (int count=1; count<=N; count++){
        for (int left=count; left>0;left--){
            for (int traveler=left-1;traveler<N - count + left; traveler++){
                if (works(left - 1, count - left, traveler)) return output_vector(left - 1, count - left, traveler);
            }
        }
    }
    
    return std::vector<int>(0);
}

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