Submission #958960

#	Time	Username	Problem	Language	Result	Execution time	Memory
958960		IUA_Hasin	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	600 KiB

molecules

#include <bits/stdc++.h>
 
#define endl                                "\n"
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define ll                                  long long
 
using namespace std; 

#include "molecules.h"

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    vector<pair<ll, ll>> v;
    for(int i=0; i<w.size(); i++){
        ll a = w[i];
        v.push_back({a, i});
    }

    sort(v.begin(), v.end());
    ll s = w.size();
    ll arr[s+1];
    arr[0] = 0;
    for(int i=0; i<s; i++){
        ll a = v[i].first;
        arr[i+1] = arr[i]+a;
    }
    // for(int i=0; i<=s; i++){
    //     cout << arr[i] << " ";
    // }
    // cout<<endl;
    ll status = -1;
    ll q, r, k;

    for(int i=0; i<s; i++){
        if(status==1){
            break;
        } else {
            ll a = arr[i+1]-arr[0];
            ll b = arr[s]-arr[s-i-1];
            // cout<<a<<" "<<b<<endl;
            if(a<=u && b>=l){
                ll aa = a;
                ll bb = 0;
                ll cnt = 0;
                q = 0;
                r = s-1;
                // cout << aa << " " << bb << " " << i << endl; 
                while(q<r || cnt<i+1){
                    if((aa+bb)>=l && (aa+bb)<=u){
                        status = 1;
                        k = i+1;
                        break;
                    } else {
                        ll c = v[q].first;
                        ll d = v[r].first;
                        aa = aa-c;
                        bb = bb+d;
                        q++;
                        r--;
                        cnt++;
                    }
                    // cout << aa << " " << bb << " " << i << endl; 
                }
            }
        }
    }
    // cout<<q<<" "<<r<<endl;


    if(status==-1){
        return std::vector<int>(0);
    } else {
        vector<int> ans;
        k--;
        for(int i=q; i<=k; i++){
            ans.push_back(v[i].second);
        }
        for(int i=s-1; i>=r+1; i--){
            ans.push_back(v[i].second);
        }
        // cout << q << " " << r << endl;
        // for(int i=0; i<ans.size(); i++){
        //     cout << ans[i] << " ";
        // }
        // cout<<endl;
        return ans;
    }

}

Compilation message (stderr)

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

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