Submission #1223473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223473		lfe	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	34 ms	4276 KiB

molecules

#include "molecules.h"
#include <vector>
#include <algorithm>
#include <queue>

using ll = long long;

using namespace std;

vector<int> qtov(queue<int>& q) {
    vector<int> ut;
    while (!q.empty()) {
        ut.push_back(q.front());
        q.pop();
    }
    return ut;
}

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = w.size();
    vector<pair<int,int>> vekter;
    for (int i = 0; i < n; i++) {
        vekter.emplace_back(w[i], i);
    }
    sort(vekter.begin(), vekter.end());

    int k = 0;
    ll tot = 0;
    queue<int> ind;
    while (tot < l && k < n) {
        tot += (ll) vekter[n-1-k].first;
        ind.push(vekter[n-1-k].second);
        k++;
    }

    if (tot <= u && tot >= l) return qtov(ind);
    else if (tot < l) return vector<int>(0);

    for (int i = 0; i < k; i++) {
        tot -= w[ind.front()];
        tot += vekter[i].first;
        ind.pop();
        ind.push(vekter[i].second);
        if (tot <= u && tot >= l) return qtov(ind);
    }
    
    return vector<int>(0);
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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