Submission #386575

#	Time	Username	Problem	Language	Result	Execution time	Memory
386575		Christopher_Rdz	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	52 ms	5612 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

struct datos{
    int valor;
    int id;
};

const bool operator <(const datos&a, const datos&b){
    return a.valor < b.valor;
}

datos arre[200005];

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    int tam = w.size();
    for (int i = 0; i < tam; i++){
        arre[i].valor = w[i];
        arre[i].id = i;
    }
    sort(arre + 0, arre + tam);
    int ini = 0, fin = 0, mayor, menor;
    long long int suma = 0;
    if (l > u){
        mayor = l;
        menor = u;
    }else{
        mayor = u;
        menor = l;
    }
    bool puede = false;
    while (fin <= tam){
        if (suma < menor){
            suma += arre[fin].valor;
            fin++;
        }else{
            if (suma > mayor){
                suma -= arre[ini].valor;
                ini++;
            }else{
                if (suma >= menor and suma <= mayor){
                    puede = true;
                    break;
                }
            }
        }
    }
    vector <int> res;
    if (puede){
        suma = 0;
        for (int i = ini; i <= fin; i++){
            if (suma < menor){
                res.push_back(arre[i].id);
                suma += arre[i].valor;
            }
        }
    }
    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