제출 #869905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869905		Matjaz	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	39 ms	6140 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;
        //printf("%d\n", count);
        if (sum(0, count) < l) {
            l_count = count + 1;
            continue;
        }
        if (u < sum(count, 0)) {
            u_count = count - 1;
            continue;
        }
        for (int left=1; left<=count;left++){
            
            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: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31