Submission #943760

#	Time	Username	Problem	Language	Result	Execution time	Memory
943760		attky	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	348 KiB

molecules

#include <bits/stdc++.h> 

using namespace std;

struct Info {
	int PosAvant = -1, TpsArrivee = -1;
	bool vu = false;
	void entree(int p, int t, bool v) {
	    PosAvant = p;
	    TpsArrivee = t;
	    vu = v;
	}
};

vector<int> find_subset(int l, int u, vector<int> w) {
	int n = w.size(), pos = 0;
	bool possible = false;
	sort(w.begin(), w.end());
	Info Tab[u+1];
	Tab[0].entree(-1, -1, true);
	for(int loop = 0; loop < n; ++loop) {
		for(int looping = u; looping >= 0; --looping) {
			if(Tab[looping].vu) {
				int suivant = looping + w[loop];
				if(suivant <= u) {
					if(!Tab[suivant].vu) {
						Tab[suivant].entree(looping, loop, true);
						if(suivant >= l) {
							possible = true;
							pos = suivant;
							break;
						}
					}
				}
			}
		}
		if(possible) {
			break;
		}
	}
	vector<int> subset;
	while(pos > 0) {
		subset.push_back(w[Tab[pos].TpsArrivee]);
		pos = Tab[pos].PosAvant;
	}
	return subset;
}

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