Submission #242746

#	Time	Username	Problem	Language	Result	Execution time	Memory
242746		Coroian_David	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	71 ms	5740 KiB

molecules

#include <bits/stdc++.h>

#include "molecules.h"

#define xx first
#define yy second

using namespace std;

typedef long long lint;

vector <int> rez;

vector <pair<int, int>> v;

int n;

int st, dr;

void getRez()
{
    sort(v.begin(), v.end());

    lint sum = 0;
    if(v[0].xx > dr)
        return;

    for(auto u : v)
        sum += u.xx;

    if(sum < st)
        return;

    sum = 0;
    int cr = 0;
    while(cr < n && sum + v[cr].xx < st)
    {
        sum += v[cr].xx;
        cr ++;
    }
    cr --;

    if(sum + v[cr + 1].xx >= st && sum + v[cr + 1].xx <= dr)
    {
        for(int i = 0; i <= cr + 1; i ++)
            rez.push_back(v[i].yy);

        return;
    }

    int j = n - 1;
    for(int i = 0; i <= cr && i < j; i ++, j --)
    {
        sum -= v[i].xx;
        sum += v[j].xx;

        if(sum >= st && sum <= dr)
        {
            for(int x = i + 1; x <= cr; x ++)
                rez.push_back(v[x].yy);

            for(int x = n - 1; x >= j; x --)
                rez.push_back(v[x].yy);

            return;
        }
    }

    return;
}

vector <int> find_subset(int l, int u, vector<int> w)
{
    st = l;
    dr = u;

    n = w.size();

    for(int i = 0; i < n; i ++)
        v.push_back({w[i], i});

    getRez();

    return rez;
}

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