В августе этого года в Казани прошла Международная олимпиада по программированию для школьников — IOI 2016. Российская команда стала второй в общем зачете.
Один из серебряных медалистов, Денис Солонков из г. Мытищи, сделал разбор задачи «Обнаружение молекул», которая предлагалась участникам олимпиады.
Денис Солонков — многократный победитель Всероссийских олимпиад по программированию и Moscow CTF School, выпускник Школы программистов, ныне студент ВШЭ.
Являясь одним из преподавателей Дениса, я попросил его сделать разбор задачи с IOI 2016.
#include <algorithm>
#include <vector>
#include <set>
#include "molecules.h" //Including grader file
using ll = long long; //A little alias to save time.
using namespace std;
vector<int> find_subset(int l, int u, vector<int> w) {
int n = w.size();
vector<pair<int, int> > weight(n);
for (int i = 0; i < n; i++) {
weight[i] = { w[i], i }; //Storing initial index for the output.
}
sort(weight.begin(), weight.end());
ll cur_sum = 0;
int bad_i;
for (bad_i = 0; bad_i < n; bad_i++) { //Locating first bad length
cur_sum += weight[bad_i].first;
if (cur_sum > u)
break;
}
if (bad_i == 0) //no solution
{
return vector<int>();
}
set<pair<int, int> > picked, remain;
ll curpicked = 0;
for (int i = 0; i < bad_i; i++) {
picked.insert(weight[i]);
curpicked += weight[i].first;
}
for (int i = bad_i; i < n; i++) {
remain.insert(weight[i]);
}
while (curpicked < l && !remain.empty()) {
if (picked.begin()->first >= remain.rbegin()->first) //Nothing left to swap
break;
//Swap the lowest and the highest elements.
curpicked += remain.rbegin()->first - picked.begin()->first;
auto el1 = *picked.begin();
auto el2 = *remain.rbegin();
picked.erase(el1);
picked.insert(el2);
remain.erase(el2);
}
if (curpicked < l){ //no solution
return vector<int>();
}
vector<int> answer;
for (auto el : picked)
answer.push_back(el.second);
return answer;
}
К сожалению, не доступен сервер mySQL