Submission #550464

#	Time	Username	Problem	Language	Result	Execution time	Memory
550464		esomer	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	54 ms	7120 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = w.size();
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++){
        v[i] = {w[i], i};
    }
    sort(v.begin(), v.end());
    ll sum = v[0].f;
    vector<ll> prefix(n);
    prefix[0] = v[0].f;
    for(int i = 1; i < n; i++){
        sum += v[i].f;
        prefix[i] = prefix[i - 1] + v[i].f;
    }
    if(sum < l || v[0].f > u) return {};
    for(int i = 0; i < n; i++){
        int lo = i;
        int hi = n - 1;
        int r = -1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(i == 0){
                if(prefix[mid] >= l && prefix[mid] <= u){
                    r = mid;
                    break;
                }else if(prefix[mid] < l) lo = mid + 1;
                else hi = mid - 1;
            }else{
                if(prefix[mid] - prefix[i - 1] >= l && prefix[mid] - prefix[i - 1] <= u){
                    r = mid;
                    break;
                }else if(prefix[mid] - prefix[i-1] < l) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        if(r != -1){
            vector<int> ans;
            for(int j = i; j <= r; j++) ans.push_back(v[j].second);
            return ans;
        }
    }
    return {};
}

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