Submission #798923

#	Time	Username	Problem	Language	Result	Execution time	Memory
798923		andecaandeci	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	42 ms	7708 KiB

molecules

#include "molecules.h" 
#include<bits/stdc++.h>

using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long, long long>
// jangan kebiasa kalah
// kalo OI, sampah aja dulu, tapi jangan menutup kemungkinan buat AC

vector<int> find_subset(int l, int u, std::vector<int> w) 
{
    int i, j, batas = 0;
    vector<long long> pref((int)w.size(), 0);
    vector<pair<int, int>> vec;
    for(i=0;i<(int)w.size();i++)
    {
        vec.push_back({w[i], i});
    }
    sort(vec.begin(), vec.end());
    for(i=0;i<(int)w.size();i++)
    {
        pref[i] = (long long)vec[i].fi;
        if(i)
        {
            pref[i] += pref[i-1];
        }
    }
    for(i=0;i<(int)w.size();i++)
    {
        if(pref[i] < (long long)l) continue;
        if((long long)l <= pref[i] and pref[i] <= (long long)u)
        {
            vector<int> res;
            for(j=0;j<=i;j++)
            {
                res.push_back(vec[j].se);
            }
            return res;
        }
        else
        {
            int lo = 1, hi = i, mid, sum = 0;
            for(mid=(lo+hi)/2;lo<=hi;mid=(lo+hi)/2)
            {
                long long cur = pref[i] - pref[mid-1];
                if(cur > (long long)u)
                {
                    lo = mid+1;
                }
                else if(cur < (long long)l)
                {
                    hi = mid-1;
                }
                else if((long long)l <= cur and cur <= (long long)u)
                {
                    vector<int> res;
                    for(j=mid;j<=i;j++)
                    {
                        res.push_back(vec[j].se);
                    }
                    return res;
                }
            }
        }
    }
    return vector<int>(0);
}

// int main()
// {
//     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//     vector<int> res = find_subset(10, 20, {15, 17, 16, 18});
//     for(auto x : res)
//     {
//         cout<<x<<endl;
//     }
// }

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:45:38: warning: unused variable 'sum' [-Wunused-variable]
   45 |             int lo = 1, hi = i, mid, sum = 0;
      |                                      ^~~
molecules.cpp:15:15: warning: unused variable 'batas' [-Wunused-variable]
   15 |     int i, j, batas = 0;
      |               ^~~~~

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