Submission #1287576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287576		vincentbucourt1	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	35 ms	6176 KiB

molecules

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

int N;
vector<pair<ll,int>> molecules; //{val, idx}
ll wMin, wMax;
ll wOn = 0;
vector<int> ans;

std::vector<int> find_subset(int l, int r, std::vector<int> w) {
    wMin = (ll)l, wMax = (ll)r;
    N = (int)w.size();
    molecules.resize(N);
    for (int i = 0; i < N; i++) {
        molecules[i] = pair<int,int>{w[i], i};
    }
    sort(molecules.begin(), molecules.end());
    int lastUsed = N;
    for (int i = N-1; i >= 0 && wOn < wMin; i--) {
        wOn += molecules[i].first;
        ans.emplace_back(molecules[i].second);
        lastUsed = i;
    }
    if (wMin <= wOn && wOn <= wMax) return ans;
    for (int i = 0; i < min(lastUsed, (int)ans.size()) && wMax < wOn; i++) {
        wOn -= molecules[N-i-1].first;
        wOn += molecules[i].first;
        ans[i] = molecules[i].second;
    }
    if (wMin <= wOn && wOn <= wMax) return ans;
    return vector<int>{};
}

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