제출 #1116671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116671		NotLinux	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	508 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    sort(w.begin() , w.end());
    int n = (int)w.size();
    long long pre[n] , suf[n];
    pre[0] = w[0];
    suf[n-1] = w[n-1];
    for(int i = 1;i<n;i++){
        pre[i] = pre[i-1] + 1ll * w[i];
    }
    for(int i = n-2;i>=0;i--){
        suf[i] = suf[i+1] + 1ll * w[i];
    }
    for(int i = 1;i<=n;i++){
        if(pre[i-1] <= u and suf[n-i] >= l){
            // cout << "size : " << i << endl;
            long long cursum = pre[i-1] , lst = n;
            vector < int > ret;
            for(int j = i-1;j>=0;j--){
                int bsl = j , bsr = lst-1;
                while(bsl < bsr){
                    int mid = (bsl + bsr) / 2;
                    // cout << "mid " << mid << " : " << cursum - w[j] + w[mid] << " > " << l << endl;
                    if((cursum - w[j] + w[mid]) > l)bsr = mid;
                    else bsl = mid+1;
                }
                cursum += w[bsl] - w[j];
                ret.push_back(bsl);
                // cout << "added : " << w[bsl] << endl;
                lst = bsl;
            }
            // cerr << "cursum : " << cursum << " , " << l << " - " << u << endl;
            assert(cursum >= l and cursum <= u);
            return ret;
        }
    }
    return vector<int>();
}

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