Submission #289126

#	Time	Username	Problem	Language	Result	Execution time	Memory
289126		amoo_safar	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	80 ms	7032 KiB

molecules

#include "molecules.h"

#include <bits/stdc++.h>

using namespace std;


const int N = 2e5 + 10;

long long mn[N], mx[N];

vector<int> find_subset(int l, int u, vector<int> W){
    int n = W.size();
    vector<int> I(n);
    iota(I.begin(), I.end(), 0);
    sort(I.begin(), I.end(), [&](int i, int j){
    	return W[i] < W[j];
    });

    sort(W.begin(), W.end());

    mn[0] = mx[0] = 0;
    for(int i = 1; i <= n; i++) mn[i] = mn[i - 1] + (W[i - 1] - W[0]);
    for(int i = 1; i <= n; i++) mx[i] = mx[i - 1] + (W[n - i] - W[0]);

    int sz = -1;
	long long A, B, L, U, sum;
    for(int i = 1; i <= n; i++){
    	A = mn[i];
    	B = mx[i];
    	L = l - (1ll * i * W[0]);
    	U = u - (1ll * i * W[0]);
    	if(B < L) continue;
    	if(U < A) continue;
    	sz = i;
    	break;
    }
    if(sz == -1)
    	return vector<int>(0);
    vector<int> res;
    
    L = l - (1ll * sz * W[0]);
    U = u - (1ll * sz * W[0]);	
    int pre = -1;
    for(int i = 0; i <= sz; i++){
    	sum = mn[i] + mx[sz - i];
    	if(L <= sum && sum <= U)
    		pre = i;
    }
	assert(pre != -1);
	for(int i = 0; i < pre; i++)
		res.push_back(I[i]);
	for(int i = 0; i < sz - pre; i++)
		res.push_back(I[n - 1 - i]);
	sort(res.begin(), res.end());
	
    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