Submission #834525

#	Time	Username	Problem	Language	Result	Execution time	Memory
834525		erdemkiraz	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	404 KiB

molecules

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

vector<int> find_subset(int L, int R, vector<int> v_o) {
  ll l = L;
  ll r = R;
  vector<ii> v;
  for(int it = 0; it < (int) v_o.size() - 1; it++) {
    v.push_back({v_o[it], it});
  }
  sort(v.begin(), v.end());

  if(v[0].first > R) return {};
  if(v[0].first >= L) return {v[0].second};
  if(v.back().first >= L) return {v[0].second};

  ll sum = 0;

  multiset<int> taken;

  int until = -1;

  for(int i = 0; i < (int) v.size(); i++) {
    if(sum + v[i].first > r) break;
    taken.insert(v[i].second);
    sum += v[i].first;
    until = i;
  }

  if(sum >= l) {
    vector<int> res;
    for(auto x : taken) {
      res.push_back(x);
    }
    return res;
  }

  if(until == -1 or (until == (int) v.size() - 1 and sum < l)) return {};

  int l_it = 0;
  int r_it = (int) v.size() - 1;

  while(sum < l and r_it > until and l_it <= until) {
    taken.insert(v[r_it].second);
    sum += v[r_it--].first;
    taken.erase(taken.find(v[l_it].second));
    sum -= v[l_it++].first;
  }

  if(sum < l) return {};
  assert(sum <= r);

  vector<int> res;
  for(auto x : taken) {
    res.push_back(x);
  }
  return res;
}

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