Submission #538041

#	Time	Username	Problem	Language	Result	Execution time	Memory
538041		pavement	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	61 ms	8568 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll P[200005];
pair<ll, ll> act[200005];

vector<int> find_subset(int l, int u, vector<int> w) {
	for (ll i = 0; i < w.size(); i++) act[i] = make_pair(w[i], i);
	sort(act, act + w.size());
	for (ll i = 0; i < w.size(); i++)
		P[i + 1] = P[i] + (ll)act[i].first;
	for (ll i = 1; i <= w.size(); i++) {
		ll lo = 0, hi = i - 1, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (P[i] - P[mid] >= (ll)l) ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (ans != -1 && P[i] - P[ans] <= u) {
			vector<int> v;
			for (ll j = ans; j < i; j++) v.push_back(act[j].second);
			return v;
		}
	}
	return vector<int>();
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:10:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for (ll i = 0; i < w.size(); i++) act[i] = make_pair(w[i], i);
      |                 ~~^~~~~~~~~~
molecules.cpp:12:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (ll i = 0; i < w.size(); i++)
      |                 ~~^~~~~~~~~~
molecules.cpp:14:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (ll i = 1; i <= w.size(); i++) {
      |                 ~~^~~~~~~~~~~

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