Submission #603851

#	Time	Username	Problem	Language	Result	Execution time	Memory
603851		strange420	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	58 ms	6172 KiB

molecules

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

typedef pair<int, int> ii;

bool func(const ii& a, const ii& b) { return a.first < b.first; }

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    vector<ii> asd;
    for (int i=0; i<w.size(); i++)
        asd.push_back(ii(w[i], i));
    sort(asd.begin(), asd.end(), func);

    vector<int> ans;
    int leftPt = 0, rightPt = 1;
    long long sum = asd[0].first;
    while(true) {
        if (sum > u) {
            sum -= asd[leftPt].first;
            leftPt++;
            if (leftPt > rightPt) break;
        } else if (sum < l) {
            if (rightPt == asd.size()) break;
            sum += asd[rightPt].first;
            rightPt++;
        } else if (l <= sum && sum <=u) {
            for (int i=leftPt; i<rightPt; i++)
                ans.push_back(asd[i].second);
            break;
        }
    }
    return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=0; i<w.size(); i++)
      |                   ~^~~~~~~~~
molecules.cpp:24:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             if (rightPt == asd.size()) break;
      |                 ~~~~~~~~^~~~~~~~~~~~~

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