Submission #388556

#	Time	Username	Problem	Language	Result	Execution time	Memory
388556		alishahali1382	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	57 ms	6076 KiB

molecules

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define pb push_back
#define all(x) x.begin(), x.end()

int n, m, k;
vector<int> out;
vector<pli> vec;

vector<int> find_subset(int l, int u, vector<int> W){
	for (int i=0; i<W.size(); i++) vec.pb({W[i], i});
	sort(all(vec));
	while (vec.size() && vec.back().first>u) vec.pop_back();
	n=vec.size();
	ll sum=0;
	while (k<n && sum+vec[k].first<l) sum+=vec[k++].first;
	if (k==n) return out; // jame kol < l
	if (sum+vec[k].first<=u){
		for (int i=0; i<=k; i++) out.pb(vec[i].second);
		return out;
	}
	for (int i=k; i<n; i++){
		sum+=vec[i].first-vec[i-k].first;
		if (sum>=l){
			for (int j=i-k+1; j<=i; j++) out.pb(vec[j].second);
			return out;
		}
	}
	// har k_ta<l
	// har k+1_ta>u
	return out;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i=0; i<W.size(); i++) vec.pb({W[i], 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