Submission #434429

#	Time	Username	Problem	Language	Result	Execution time	Memory
434429		vanic	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	74 ms	3564 KiB

molecules

#include "molecules.h"
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn=2e5+5;
typedef long long ll;

int n;
vector < int > v;
vector < int > sol;
int pos[maxn];

bool cmp(int a, int b){
	return v[a]<v[b];
}

vector < int > find_subset(int l, int u, vector < int > w) {
	v=w;
	n=v.size();
	for(int i=0; i<n; i++){
		pos[i]=i;
	}
	sort(pos, pos+n, cmp);
	ll sum=0;
	int ind;
	for(int i=0; i<n; i++){
		ind=i;
		sum+=v[pos[i]];
		if(sum>l){
			break;
		}
	}
	if(sum<l){
		return sol;
	}
	if(sum>u){
		sum-=v[pos[ind]];
		if(!sum){
			return sol;
		}
	}
	else{
		ind++;
	}
	int ind2=0;
	while(ind<n && sum<l){
		sum+=v[pos[ind]]-v[pos[ind2]];
		ind2++;
		ind++;
	}
//	cout << ind2 << ' ' << ind << endl;
	if(sum<l){
		return sol;
	}
	for(int i=ind2; i<ind; i++){
		sol.push_back(pos[i]);
	}
	return sol;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:30:6: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |  int ind;
      |      ^~~

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