Submission #650715

#	Time	Username	Problem	Language	Result	Execution time	Memory
650715		Markomafko972	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	51 ms	7100 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

ll pref[200005];
pair<int, int> p[200005];

vector<int> ispis(int poc, int kr) {
	vector<int> sol;
	
	for (int i = poc; i <= kr; i++) {
		sol.push_back(p[i].Y);
	}
	
	return sol;
}

vector<int> find_subset(int l, int u, vector<int> w) {
	reverse(w.begin(), w.end());
	w.push_back(0);
	reverse(w.begin(), w.end());
	
	for (int i = 0; i < w.size(); i++) {
		p[i] = {w[i], i-1};
	}
	sort(p, p + (int)w.size());
	
	int n = (int)w.size()-1;
	for (int i = 1; i < (int)w.size(); i++) {
		pref[i] = pref[i-1] + p[i].X;
	}
	
	for (int i = 1; i <= n; i++) {
		ll d = pref[i];
		ll g = pref[n] - pref[n-i];
		
		if (d >= l && d <= u) return ispis(1, i);
		if (g >= l && g <= u) return ispis(n-i+1, n);
		if (d < l && g > u) {
			for (int j = i+1; j <= n; j++) {
				d = d + p[j].X - p[j-i].X;
				if (d >= l && d <= u) return ispis(j-i+1, j);
			}
		}
	}
	
	vector<int> prazan;
	prazan.clear();
	return prazan;
}

Compilation message (stderr)

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