Submission #296723

#	Time	Username	Problem	Language	Result	Execution time	Memory
296723		Haunted_Cpp	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	72 ms	7160 KiB

molecules

#include <bits/stdc++.h>

#include "molecules.h"
using namespace std;

vector<int> find_subset(int lo, int hi, vector<int> w) {
  const int n = w.size();
  vector<pair<int, int>> arr(n);
  for (int i = 0; i < n; i++) {
    arr[i] = {w[i], i};
  }
  sort(arr.begin(), arr.end());
  vector<long long> dp(n);
  dp[0] = arr[0].first;
  for (int i = 1; i < n; i++) {
    dp[i] = arr[i].first + dp[i - 1];
  }
  auto range_sum = [&](int l, int r) {
    if (l >= n) return 0LL;
    return dp[r] - (l - 1 >= 0 ? dp[l - 1] : 0LL);
  };
  long long s = 0;
  for (int i = 0; i <= n; i++) {
    int l = i + 1;
    int r = n;
    while(l < r) {
      const int mid = l + (r - l) / 2;
      long long add = range_sum(mid, n - 1);
      if (s + add <= hi) r = mid;
      else l = mid + 1;
    }
    s += range_sum(r, n - 1);
    if (s >= lo && s <= hi) {
      vector<int> res;
      for (int x = 0; x < i; x++) {
        res.emplace_back(arr[x].second);
      }
      for (int x = r; x < n; x++) {
        res.emplace_back(arr[x].second);
      }
      return res;
    }
    s += arr[i].first;
    s -= range_sum(r, n - 1);
  }
  return vector<int>();
}

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