Submission #746305

#	Time	Username	Problem	Language	Result	Execution time	Memory
746305		Sami_Massah	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	336 KiB

molecules

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


const long long maxn = 2e5 + 12, mod = 998244353, inf = 1e9 + 12 ;
long long mn[maxn], mx[maxn];
vector <int> ans, f;
vector <pair<int, int>> a2;

vector <int> find_subset(int l, int r, vector <int> a){
    int n = a.size();
    for(int i = 0; i < n; i++)
        a2.push_back(make_pair(a[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] = a[n - 1];
    for(int i = n - 2; i >= 0; i--)
        mx[i] = mx[i + 1] + a2[i].first;
    for(int i = 1; i <= n; i++){
        if(mn[i - 1] <= r && 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 > r){
                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;



}

Compilation message (stderr)

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

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