Submission #255297

#	Time	Username	Problem	Language	Result	Execution time	Memory
255297		niyu	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	80 ms	8424 KiB

molecules

/*
5 10 20 
2 2 2 2 2
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
#include "molecules.h"

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
const ld PI = 4*atan((ld)1);

vi res;
ll lf, rt, len, N;
vpl ww;

vi find_subset(int l, int u, vi w) {
	N = sz(w);
	F0R(i, N) ww.pb({w[i], i});
	sort(all(ww));
	len = -1;
	F0R(i, N) {
		lf += ww[i].f;
		rt += ww[N - i - 1].f;
		if (rt < l || u < lf) continue;
		len = (i + 1);
		break;
	}
	//cout << "LEN: " << len << '\n';
	//cout << "LF: " << lf << '\n';
	if (len == -1) return res;
	F0R(i, N - len + 1) {
		if (l <= lf && lf <= u) {
			FOR(j, i, i + len) {
				res.pb(ww[j].s);
			}
			break;
		}
		lf += ww[i + len].f - ww[i].f; 
	}
	return res;
}

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