Submission #145463

#	Time	Username	Problem	Language	Result	Execution time	Memory
145463		MathStudent2002	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	65 ms	8696 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"

using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second

typedef long long ll;
typedef pair<ll,ll> pi;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    int N = w.size();
    pi wt[N];

    vector<int>::iterator it = w.begin();
    for(int i = 0; i < N; i++) {
        wt[i] = mp(*it,i);
        it++;
    }

    sort(wt,wt+N);

    vector<int> ans;

    if(wt[0].x > u) return ans;
    ll tot[N+1];
    ll cur;
    tot[0] = wt[0].x;

    for(int i = 1; i < N; i++) {
        tot[i] = tot[i-1] + wt[i].x;
    }

    tot[N] = ((ll)(u))+1;

    int look = -1;
    for(int i = N; i >= 0; i--)
        if(look == -1 && tot[i] <= u) {look = i; cur = tot[i];}

    int found = -1;

    for(int i = look; i < N; i++) {
        if(cur >= l && found == -1) {found = i;}
        if(i+1 < N) {cur += wt[i+1].x - wt[i-look].x;}
    }

    if(found == -1) return ans;

    for(int j = found-look; j <= found; j++) {ans.pb(wt[j].y);}

    return ans;
}

/*
int main() {
    int n, l, u;
    assert(3 == scanf("%d %d %d", &n, &l, &u));
    std::vector<int> w(n);
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &w[i]));
    std::vector<int> result = find_subset(l, u, w);


    printf("%d\n", (int)result.size());
    for (int i = 0; i < (int)result.size(); i++)
        printf("%d%c", result[i], " \n"[i == (int)result.size() - 1]);
}*/

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:46:9: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(cur >= l && found == -1) {found = 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