Advertisement
Shaktal

Behaviour Difference in GCC vs VS

Jan 19th, 2015
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.27 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <limits>
  7. #include <string>
  8. #include <sstream>
  9. #include <unordered_set>
  10.  
  11. int main() {
  12.     unsigned int iNumCases;
  13.     std::cin >> iNumCases;
  14.    
  15.     while( iNumCases-- )
  16.     {
  17.         unsigned int iMoney, iNumFlavours;
  18.         std::cin >> iMoney >> iNumFlavours;
  19.         std::vector<unsigned int> vecFlavourPrices( iNumFlavours );
  20.        
  21.         // Clear Input:
  22.         std::cin.clear();
  23.         std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' );
  24.        
  25.         // Populate flavour-price vector:
  26.         {
  27.             std::string szLine;
  28.             std::getline( std::cin, szLine );
  29.             std::stringstream ss( std::move(szLine) );
  30.            
  31.             for( unsigned int i = 0; i < iNumFlavours; ++i )
  32.             {
  33.                 ss >> vecFlavourPrices[i];
  34.             }
  35.         }
  36.        
  37.         // Using a hash-table allows us to look up in O(1) time:
  38.         std::unordered_set<unsigned int> setFlavourPrices( vecFlavourPrices.cbegin(), vecFlavourPrices.cend() );
  39.        
  40.         unsigned int iPrice1, iPrice2;
  41.         for( unsigned int i : setFlavourPrices )
  42.         {
  43.             // See if the conjugate for the pair is in the set:
  44.             if( setFlavourPrices.find( iMoney - i ) != setFlavourPrices.end() )
  45.             {
  46.                 iPrice1 = i;
  47.                 iPrice2 = iMoney - i;
  48.                 break;
  49.             }
  50.         }
  51.        
  52.         // Now find the indices of the two prices in the initial vector - O(n):
  53.         std::size_t sIndex1 = std::numeric_limits<std::size_t>::max(), sIndex2 = std::numeric_limits<std::size_t>::max();
  54.        
  55.         if( iPrice1 != iPrice2 )
  56.         {
  57.             for( std::size_t s = 0; s < vecFlavourPrices.size(); ++s )
  58.             {
  59.                 if( vecFlavourPrices[s] == iPrice1 )
  60.                 {
  61.                     sIndex1 = s;
  62.                    
  63.                     // Are we done?
  64.                     if( sIndex2 < std::numeric_limits<std::size_t>::max() )
  65.                         break;
  66.                 }
  67.                 else if( vecFlavourPrices[s] == iPrice2 )
  68.                 {
  69.                     sIndex2 = s;
  70.                    
  71.                     // Are we done?
  72.                     if( sIndex1 < std::numeric_limits<std::size_t>::max() )
  73.                         break;
  74.                 }
  75.             }
  76.         }
  77.         else
  78.         {
  79.             // We have to be careful to get two distinct indices:
  80.             bool bGotFirst = false;
  81.             for( std::size_t s = 0; s < vecFlavourPrices.size(); ++s )
  82.             {
  83.                 if( vecFlavourPrices[s] == iPrice1 )
  84.                 {
  85.                     if( !bGotFirst )
  86.                     {
  87.                         sIndex1 = s;
  88.                         bGotFirst = true;
  89.                     }
  90.                     else
  91.                     {
  92.                         sIndex2 = s;
  93.                         break;
  94.                     }
  95.                 }
  96.             }
  97.         }
  98.        
  99.         if( sIndex1 > sIndex2 )
  100.             std::swap( sIndex1, sIndex2 );
  101.        
  102.         std::cout << sIndex1+1 << " " << sIndex2+1 << std::endl;
  103.     }
  104.    
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement