Submission #958961

#	Time	Username	Problem	Language	Result	Execution time	Memory
958961		IUA_Hasin	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	45 ms	9748 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;
    }
    ll status = -1;
    ll q, r, k;
    ll aa, bb;

    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];
            if(a<=u && b>=l){
                aa = a;
                bb = 0;
                ll cnt = 0;
                q = 0;
                r = s-1;
                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++;
                    }
                }
                if((aa+bb)>=l && (aa+bb)<=u){
                    status = 1;
                    k = i+1;
                    break;
                }

            }
        }
    }


    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);
        }
        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: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31