Submission #644373

#	Time	Username	Problem	Language	Result	Execution time	Memory
644373		vladislav11	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1 ms	304 KiB

molecules

#include <bits/stdc++.h>

using namespace std;

vector<int> find_subset ( int l, int r, vector<int> w )
{
    vector<int> old = w;
    sort( w.begin(), w.end(), greater<int>() );
    
    vector<int> a, b;
    
    for ( auto& el : w )
    {
        if ( l >= el )
        {
            l -= el;
            r -= el;
            a.push_back(el);
        }
        else
            b.push_back(el);
    }
    
    /*for ( auto& el : a )
        cout << el << ' ';
    cout << '\n';
    
    for ( auto& el : b )
        cout << el << ' ';
    cout << '\n';*/
    
    if ( b.size() && b.back() <= r )
    {
        l -= b.back();
        r -= b.back();
        a.push_back( b.back() );
        b.pop_back();
    }
    
    //cout << "! " << l << ' ' << r << '\n';
    
    if ( 0 < l || r < 0 )
        return {};
    
    vector<int> ans;
    multiset<int> mst( a.begin(), a.end() );
    
    /*for ( auto& el : mst )
        cout << el << ' ';
    cout << '\n';*/
    
    for ( int i=0; i<old.size(); i++ )
    if ( mst.count( old[i] ) )
    {
        mst.erase(mst.find( old[i] ));
        ans.push_back(i+1);
    }
    
    return ans;
}

Compilation message (stderr)

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

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