Submission #229220

#	Time	Username	Problem	Language	Result	Execution time	Memory
229220		tushar_2658	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	73 ms	7272 KiB

molecules

#include "molecules.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	int N = w.size();
  vector<pair<int, int>> a;
  for(int i = 0; i < N; ++i){
    a.push_back(make_pair(w[i], i));
  }
  sort(a.begin(), a.end());
  vector<ll> pref(N + 2);
  vector<int> v;
  for(int i = 1; i <= N; ++i){
    pref[i] = pref[i - 1] + a[i - 1].first;
  }
  for(int i = 1; i <= N; ++i){
    int lo = 0, hi = i, ans = -1;
    while(lo <= hi){
      int mid = (lo + hi) >> 1;
      if(pref[i] - pref[mid] >= l && pref[i] - pref[mid] <= u){
        ans = mid;
        break;
      }else if(pref[i] - pref[mid] < l){
        hi = mid - 1;
      }else if(pref[i] - pref[mid] > u){
        lo = mid + 1;
      }
    }
    if(ans != -1){
      for(int j = ans; j < i; ++j){
        v.push_back(a[j].second);
      }
      break;
    }
  }
  sort(v.begin(), v.end());
  return v;
}

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