Submission #70037

#	Time	Username	Problem	Language	Result	Execution time	Memory
70037		chpipis	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	97 ms	32680 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 5;

vector<int> w;
ll pref[MAXN];

inline bool comp(int a, int b) {
	return w[a] < w[b];
}

vector<int> find_subset(int l, int u, vector<int> _w) {
	w = _w;
	int n = (int)w.size();
    vector<int> p(n);
    for (int i = 0; i < n; i++)
    	p[i] = i;
   	sort(p.begin(), p.end(), comp);
   	pref[0] = w[p[0]];
   	for (int i = 1; i < n; i++) {
   		pref[i] = pref[i - 1] + w[p[i]];
   	}
   	int j = 0;
   	for (int i = 0; i < n; i++) {
   		j = max(j, i);
   		while (j + 1 < n && pref[j] - (i == 0 ? 0 : pref[i - 1]) < l)
   			j++;
   		ll sum = pref[j] - (i == 0 ? 0 : pref[i - 1]);
   		if (sum >= ( ll )l && sum <= ( ll )u) {
   			vector<int> ans;
   			for (int k = i; k <= j; k++)
   				ans.push_back(p[k]);
   			return ans;
   		}
   	}
   	return vector<int>();
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:21:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < n; i++)
     ^~~
molecules.cpp:23:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     sort(p.begin(), p.end(), comp);
     ^~~~

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