Submission #746308

#	Time	Username	Problem	Language	Result	Execution time	Memory
746308		Sami_Massah	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	1081 ms	9280 KiB

molecules

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


const long long maxn = 2e5 + 12, mod = 998244353, inf = 1e9 + 12 ;

vector <int> find_subset(int l, int u, vector <int> w){
    long long mn[200000 + 12], mx[200000 + 12];
    vector <int> ans, f;
    vector <pair<int, int>> a2;

    int n = w.size();
    for(int i = 0; i < n; i++)
        a2.push_back(make_pair(w[i], i));
    sort(a2.begin(), a2.end());
    mn[0] = a2[0].first;
    for(int i = 1; i < n; i++)
        mn[i] = mn[i - 1] + a2[i].first;
    mx[n - 1] = a2[n - 1].first;
    for(int i = n - 2; i >= 0; i--)
        mx[i] = mx[i + 1] + a2[i].first;
    for(int i = 1; i <= n; i++){
     //   cout << mn[i - 1] << ' ' << mx[n - i] << endl;
        if(mn[i - 1] <= u && l <= mx[n - i]){
            long long sum = mx[n - i];
            for(int j = n - i; j < n; j++)
                ans.push_back(j);
            int loc = 0;
            while(sum < l || sum > u){
                if(ans[loc] == loc){
                    loc += 1;
                }
                else{
                    int now = ans[loc];
                    sum = sum - a2[now].first + a2[now - 1].first;
                    ans[loc] -= 1;
                }
            }
            for(int j = 0; j < ans.size(); j++){
                //cout << ans[j] << endl;
                ans[j] = a2[ans[j]].second;

                }
          //  cout << endl;
            return ans;

        }

    }
    return ans;



}
/*
int main(){
    vector <int> f;
    int n, l, r;
    cin >> n >> l >> r;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        f.push_back(a);

    }
    vector <int> nat = find_subset(l, r, f);
    for(int i: nat)
        cout << i << ' ';


}
*/

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int j = 0; j < ans.size(); j++){
      |                            ~~^~~~~~~~~~~~

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