Submission #869913

#	Time	Username	Problem	Language	Result	Execution time	Memory
869913		Matjaz	Detecting Molecules (IOI16_molecules)	C++14	9 / 100	1073 ms	504 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];
    
    int l_count = 1;
    int u_count = N;
 
    while (l_count <= u_count){
        
        int count = l_count + (u_count - l_count) / 2;
        if (sum(0, count) < l) {
            l_count = count + 1;
            continue;
        }
        if (u < sum(count, 0)) {
            u_count = count - 1;
            continue;
        }
        
        int l_left = 1;
        int u_left = count;
        
        while (l_left <= u_left){
            int left = l_left + (u_left - l_left) / 2;
            
            if (sum(left, count - left) > u){
                u_left = left - 1;
                continue;
            }
            if (sum(left - 1, count - left + 1 ) < l){
                l_left = left + 1;
                continue;
            }
            
            int l_traveler = left - 1;
            int u_traveler = N - count + left - 1;
            
            while (l_traveler <= u_traveler){
                int traveler = l_traveler + (u_traveler - l_traveler) / 2;
                if (works(left - 1, count - left, traveler)) return output_vector(left - 1, count - left, traveler);
                
                if (sum(left - 1 , count - left) + w[traveler] < l){
                    l_traveler = traveler + 1;
                } else u_traveler = traveler - 1;
            }
        }
    }
    
    return std::vector<int>(0);
}

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