Submission #1080666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080666		asdasdqwer	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	146 ms	27480 KiB

molecules

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

#include "molecules.h"

#define ll long long

vector<int> indi(vector<ll> &weigh, map<int,vector<int>> &mp) {
    vector<int> ind;
    for (auto &x:weigh) {
        ind.push_back(mp[x].back());mp[x].pop_back();
    }
    return ind;
}



std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    int n=(int)w.size();
    map<int,vector<int>> mp;
    for (int i=0;i<n;i++) {
        mp[w[i]].push_back(i);
    }

    sort(w.begin(), w.end());

    vector<ll> p(n);
    p[0]=w[0];
    for (int i=1;i<n;i++) {
        p[i] = p[i-1]+w[i];
    }

    if (p[0] > u || p.back() < l) return {};

    // check if some prefix becomes possible
    for (int i=0;i<n;i++) {
        if (l <= p[i] && p[i] <= u) {
            vector<ll> we;
            for (int j=0;j<=i;j++) we.push_back(w[j]);
            return indi(we, mp);
        }
    }

    vector<ll> we;
    for (int i=0;p[i]<l && i<n;i++) {
        we.push_back(w[i]);
    }

    int pt = 0, idx = (int)we.size();
    ll sum = p[idx-1];
    for (int i=idx;i<n;i++) {
        sum += w[i] - we[pt];
        we[pt] = w[i];

        if (l <= sum && sum <= u) return indi(we, mp);
        pt++;
        pt %= idx;
    }

    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