Submission #54505

#	Time	Username	Problem	Language	Result	Execution time	Memory
54505		MoNsTeR_CuBe	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	62 ms	31144 KiB

molecules

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

using namespace std;

vector<int> find_subset(int l, int r, vector<int> w){
    int n = w.size();
    vector< pair<int, int> > v(n);
    for(int i = 0; i < n; i++){
        v[i] = make_pair(w[i],i);
    }
    sort(v.begin(), v.end());
    vector<bool> taken(n, false);
    int left = 0, right = 0;
    long long tot = 0;
    while(1){
        while(right < n && tot < (long long) l){
            tot+=(long long) v[right].first;
            taken[v[right].second] = true;
            right++;
        }
        while(left < n && tot > (long long) r){
            tot-=(long long) v[left].first;
            taken[v[left].second] = false;
            left++;
        }
        if(tot >= l && tot <= r){
            vector<int> ans(0);
            for(int i = 0; i < n; i++){
                if(taken[i]) ans.push_back(i);
            }
            return ans;
        }
        if(left >= n || right >= n) break;
    }
    vector<int> ans(0);
    return ans;
}
/*
signed main(){
    int a, b, c;
    cin >> a >> b >> c;
    vector<int> v(0);
    for(int i = 0; i < a; i++){
        int d;
        cin >> d;
        v.push_back(d);
    }
    v = find_subset(b,c,v);
    cout << v.size() << endl;
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ' ';
    }
    cout << endl;
}*/

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