Submission #834518

#	Time	Username	Problem	Language	Result	Execution time	Memory
834518		erdemkiraz	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	0 ms	212 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) {
  ll l = L;
  ll r = R;
  sort(v.begin(), v.end());

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

  ll sum = 0;

  multiset<int> taken;

  int until = -1;

  for(int i = 0; i < (int) v.size(); i++) {
    if(sum + v[i] > r) break;
    taken.insert(v[i]);
    sum += v[i];
    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]);
    sum += v[r_it--];
    taken.erase(taken.find(v[l_it]));
    sum -= v[l_it++];
  }

  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