Submission #77091

#	Time	Username	Problem	Language	Result	Execution time	Memory
77091		shoemakerjo	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1070 ms	836 KiB

molecules

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

#define ll long long
using namespace std;

map<ll, set<int>> indos;

vector<int> find_subset(int l, int u, vector<int> w) {
    sort(w.begin(), w.end());
    multiset<ll> curin;
    multiset<ll> curout;
    ll csum = 0;

    for (int i = 0; i < w.size(); i++) {
    	if (indos.count(w[i])) {
    		indos[w[i]].insert(i);
    	}
    	else {
    		set<int> stuff;
    		stuff.insert(i);
    		indos[w[i]] = stuff;

    	}
    	curout.insert(w[i]);
    }

    while (csum < l) {
    	if (curout.size() == 0) break;
    	if (csum + *curout.begin() <= u) {
    		csum += *curout.begin();
    		curin.insert(*curout.begin());
    		curout.erase(curout.begin());
    	}
    	else {
    		ll val = *curout.rbegin();
    		ll oval = *curin.begin();
    		if (val <= oval) break;
    		csum += val-oval;
    		curout.erase(--curout.end());
    		curin.erase(curin.begin());
    		curin.insert(val);
    		curout.insert(oval);
    	}
    }
    if (csum < l) {
    	vector<int> ans;
    	return ans;
    }
    vector<int> ans;
    for (ll vv : curin) {
    	ans.push_back(*indos[vv].begin());
    	indos[vv].erase(indos[vv].begin());
    }
    return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < w.size(); i++) {
                     ~~^~~~~~~~~~

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