Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <limits>
- #include <string>
- #include <sstream>
- #include <unordered_set>
- int main() {
- unsigned int iNumCases;
- std::cin >> iNumCases;
- while( iNumCases-- )
- {
- unsigned int iMoney, iNumFlavours;
- std::cin >> iMoney >> iNumFlavours;
- std::vector<unsigned int> vecFlavourPrices( iNumFlavours );
- // Clear Input:
- std::cin.clear();
- std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' );
- // Populate flavour-price vector:
- {
- std::string szLine;
- std::getline( std::cin, szLine );
- std::stringstream ss( std::move(szLine) );
- for( unsigned int i = 0; i < iNumFlavours; ++i )
- {
- ss >> vecFlavourPrices[i];
- }
- }
- // Using a hash-table allows us to look up in O(1) time:
- std::unordered_set<unsigned int> setFlavourPrices( vecFlavourPrices.cbegin(), vecFlavourPrices.cend() );
- unsigned int iPrice1, iPrice2;
- for( unsigned int i : setFlavourPrices )
- {
- // See if the conjugate for the pair is in the set:
- if( setFlavourPrices.find( iMoney - i ) != setFlavourPrices.end() )
- {
- iPrice1 = i;
- iPrice2 = iMoney - i;
- break;
- }
- }
- // Now find the indices of the two prices in the initial vector - O(n):
- std::size_t sIndex1 = std::numeric_limits<std::size_t>::max(), sIndex2 = std::numeric_limits<std::size_t>::max();
- if( iPrice1 != iPrice2 )
- {
- for( std::size_t s = 0; s < vecFlavourPrices.size(); ++s )
- {
- if( vecFlavourPrices[s] == iPrice1 )
- {
- sIndex1 = s;
- // Are we done?
- if( sIndex2 < std::numeric_limits<std::size_t>::max() )
- break;
- }
- else if( vecFlavourPrices[s] == iPrice2 )
- {
- sIndex2 = s;
- // Are we done?
- if( sIndex1 < std::numeric_limits<std::size_t>::max() )
- break;
- }
- }
- }
- else
- {
- // We have to be careful to get two distinct indices:
- bool bGotFirst = false;
- for( std::size_t s = 0; s < vecFlavourPrices.size(); ++s )
- {
- if( vecFlavourPrices[s] == iPrice1 )
- {
- if( !bGotFirst )
- {
- sIndex1 = s;
- bGotFirst = true;
- }
- else
- {
- sIndex2 = s;
- break;
- }
- }
- }
- }
- if( sIndex1 > sIndex2 )
- std::swap( sIndex1, sIndex2 );
- std::cout << sIndex1+1 << " " << sIndex2+1 << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement