Submission #472438

#	Time	Username	Problem	Language	Result	Execution time	Memory
472438		marcipan5000	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	61 ms	6040 KiB

molecules

#include <bits/stdc++.h>

using namespace std;

struct elem{
    int e,p;
};

bool kis(elem a,elem b) {
    return((a.e<b.e)||((a.e==b.e)&&(a.p<b.p)));
}

vector<int> cut(int s,vector<int> r) {
    vector<int> ans;
    for (int i=s;i<r.size();i++) {
        ans.push_back(r[i]);
    }
    return(ans);
}

vector<int> find_subset(int l,int u,vector<int> w) {
    vector<elem> q; q.clear();
    vector<int> ans; ans.clear();
    int n=w.size();
    q.resize(n);
    for (int i=0;i<n;i++) {
        q[i].e=w[i];
        q[i].p=i;
    }
    sort(q.begin(),q.end(),kis);
    int su=0,k=0,s=0;
    while (k<n) {
        su+=q[k].e;
        ans.push_back(q[k].p);
        k++;
        if (su>u) {
            su-=q[s].e;
            s++;
        }
        if ((l<=su)&&(su<=u)) {
            return(cut(s,ans));
        }
    }
    ans.clear();
    return(ans);
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> cut(int, std::vector<int>)':
molecules.cpp:15:19: 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=s;i<r.size();i++) {
      |                  ~^~~~~~~~~

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