Submission #430537

#	Time	Username	Problem	Language	Result	Execution time	Memory
430537		APROHACK	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	63 ms	6164 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define peso first
#define pos second
#define PB push_back
using namespace std;
int ll, uu;
bool check(int a){
    return (a>=ll&&a<=uu);
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    ll=l, uu=u;
    vector<int>rta;
    vector<pair<int, int > > vc;
    for(int i =0  ; i < w.size() ; i++){
        vc.PB({w[i], i});
    }
    sort(vc.begin(), vc.end());
    long long sum = 0;
    for(int i = 0 ; i < w.size() ; i++){
        sum+=w[i];
    }
    if(vc[0].peso>u||sum<l)return rta;
    int i=0, j=0;
    long long sm = vc[j].peso;
    while(sm<l&&i<w.size()&&j<w.size()){
        while(vc[j+1].peso+sm>u&&i<w.size()&&j<w.size()){
            i++;
            sm-=vc[i-1].peso;
            if(check(sm))break;
        }
        if(check(sm))break;
        sm+=vc[j+1].peso;
        j++;
        if(check(sm))break;
    }
    if(!check(sm))return rta;
    for(int x = i ; x <= j; x++){
        rta.PB(vc[x].pos);
    }
    return rta;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i =0  ; i < w.size() ; i++){
      |                     ~~^~~~~~~~~~
molecules.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0 ; i < w.size() ; i++){
      |                     ~~^~~~~~~~~~
molecules.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(sm<l&&i<w.size()&&j<w.size()){
      |                 ~^~~~~~~~~
molecules.cpp:26:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(sm<l&&i<w.size()&&j<w.size()){
      |                             ~^~~~~~~~~
molecules.cpp:27:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while(vc[j+1].peso+sm>u&&i<w.size()&&j<w.size()){
      |                                  ~^~~~~~~~~
molecules.cpp:27:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while(vc[j+1].peso+sm>u&&i<w.size()&&j<w.size()){
      |                                              ~^~~~~~~~~

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