Submission #1116673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116673		NotLinux	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	40 ms	8784 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) {
    int n = (int)w.size();
    pair < int , int > bruh[n];
    for(int i = 0;i<n;i++)bruh[i] = {w[i] , i};
    sort(bruh , bruh + n);
    long long pre[n] , suf[n];
    pre[0] = bruh[0].first;
    suf[n-1] = bruh[n-1].first;
    for(int i = 1;i<n;i++){
        pre[i] = pre[i-1] + 1ll * bruh[i].first;
    }
    for(int i = n-2;i>=0;i--){
        suf[i] = suf[i+1] + 1ll * bruh[i].first;
    }
    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 - bruh[j].first + bruh[mid].first) > l)bsr = mid;
                    else bsl = mid+1;
                }
                cursum += bruh[bsl].first - bruh[j].first;
                ret.push_back(bruh[bsl].second);
                // cout << "added : " << w[bsl] << endl;
                lst = bsl;
            }
            // cerr << "cursum : " << cursum << " , " << l << " - " << u << endl;
            assert(cursum >= l and cursum <= u);
            int check = 0;
            for(auto itr : ret)check += w[itr];
            assert(cursum == check);
            // cerr << "cursum : " << cursum << " , " << check << endl;
            return ret;
        }
    }
    return vector<int>();
}

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