Submission #1035789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035789		DeathIsAwe	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	2 ms	772 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pair<int,int>> arr;
    int n = w.size(), temp = 0;
    for (int i=0;i<n;i++) {
        arr.push_back(make_pair(w[i],i));
    }
    sort(arr.begin(), arr.end());
    vector<int> prefix(n);
    for (int i=0;i<n;i++) {
        temp += arr[i].first;
        prefix[i] = temp;
    }


    
    vector<int> ansarr;
    if (n == 1) {
        if (l <= w[0] && w[0] <= u) {
            ansarr.push_back(0);
            return ansarr;
        } else {
            return ansarr;
        }
    }
    int bottom = 0, top = n-1, middle, base;
    while (bottom + 1 < top) {
        middle = (bottom + top)/2;
        if (prefix[middle] <= l) {
            bottom = middle;
        } else if (prefix[middle] <= u) {
            for (int i=0;i<middle+1;i++) {
                ansarr.push_back(arr[i].second);
            }
            return ansarr;
        } else {
            top = middle;
        }
    }
    //cout << top << ' ' << bottom << '\n';
    if (prefix[top] < l) {
        base = top;
    } else if (prefix[top] <= u) {
        for (int i=0;i<top+1;i++) {
            ansarr.push_back(arr[i].second);
        }
        return ansarr;
    } else if (prefix[bottom] < l) {
        base = bottom;
    } else if (prefix[bottom] <= u) {
        for (int i=0;i<bottom+1;i++) {
            ansarr.push_back(arr[i].second);
        }
        return ansarr;
    } else {
        return ansarr;
    }


    
    int anstotal = prefix[base], anstart = 0;
    for (int i=0;i<n-base;i++) {
        if (anstotal < l) {
            if (i == n-base-1) {
                return ansarr;
            }
            anstotal = prefix[i+base+1] - prefix[i];
        } else {
            anstart = i;
            break;
        }
    }



    int gap = anstart-1;
    for (int i=0;i<base+1;i++) {
        if (anstotal < u) {
            for (int j=anstart-1;j<anstart+base+1;j++) {
                if (j == gap) {
                    continue;
                }
                ansarr.push_back(arr[j].second);
            }
            break;
        } else {
            anstotal += arr[gap].first - arr[gap+1].first;
        }
    }
    return ansarr;
}

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