Submission #391519

#	Time	Username	Problem	Language	Result	Execution time	Memory
391519		giorgikob	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	64 ms	8864 KiB

molecules

#include "molecules.h"

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {

    vector<pair<int,int>>P;
    for(int i = 0; i < w.size(); i++){
        P.pb({w[i],i});
    }

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

    for(int i = 0; i < w.size(); i++) w[i] = P[i].ff;

    if(w[0] > u) return {};

    vector<int>answer;

    ll sum = 0;
    for(auto a : w) sum += a;
    if(sum < l) return {};

    vector<ll>pre(w.size(),0);
    pre[0] = w[0];
    for(int i = 1; i < w.size(); i++){
        pre[i] = pre[i-1] + w[i];
        if(pre[i] >= l && pre[i] <= u){
            for(int j = 0; j <= i; j++) answer.pb(P[j].ss);
            return answer;
        }
    }


    sum = 0;
    for(int i = w.size() - 1; i >= 0; i--){
        sum += w[i];
        answer.pb(P[i].ss);
        if(sum >= l && sum <= u) return answer;
        int L = 0, r = i-1, res = -1;
        while(L <= r){
            int mid = (L+r)/2;
            if(pre[mid] + sum >= l){
                res = mid;
                r = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        if(pre[res]+sum <= u){
            for(int j = 0; j <= res; j++){
                answer.pb(P[j].ss);
            }
            return answer;
        }
    }

    return {};
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < w.size(); i++){
      |                    ~~^~~~~~~~~~
molecules.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < w.size(); i++) w[i] = P[i].ff;
      |                    ~~^~~~~~~~~~
molecules.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 1; i < w.size(); i++){
      |                    ~~^~~~~~~~~~

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