At first I got lots of WA #1 at this problem, but I was confident in my algo.

When I replaced stl::merge with stl::sort, I got AC.
When I replaced stl::merge with stl::inplace_merge, I got AC, too.
After that, I tried to rewrite the stl::merge myself, and also got AC.
Then I copied the source code of stl::merge from "include\c++\3.4.2\bits\stl_algo.h", and ... also AC.

Does it mean that there is something strange in stl::merge of Visual C++ 2010?


UPD: I have found that the stl::merge in Visual C++ 2010 sometimes will modify the elements in the origin vector. Be careful to use it!

PS:

/* G++ merge */

  template<typename _InputIterator1, typename _InputIterator2,
       typename _OutputIterator>
    _OutputIterator
    merge(_InputIterator1 __first1, _InputIterator1 __last1,
      _InputIterator2 __first2, _InputIterator2 __last2,
      _OutputIterator __result)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
        typename iterator_traits<_InputIterator1>::value_type>)
      __glibcxx_function_requires(_SameTypeConcept<
        typename iterator_traits<_InputIterator1>::value_type,
        typename iterator_traits<_InputIterator2>::value_type>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_InputIterator1>::value_type>)
      __glibcxx_requires_sorted(__first1, __last1);
      __glibcxx_requires_sorted(__first2, __last2);

      while (__first1 != __last1 && __first2 != __last2)
    {
      if (*__first2 < *__first1)
        {
          *__result = *__first2;
          ++__first2;
        }
      else
        {
          *__result = *__first1;
          ++__first1;
        }
      ++__result;
    }
      return std::copy(__first2, __last2, std::copy(__first1, __last1,
                            __result));
    }


/* VC++ 2010 merge */

template<class _InIt1,
    class _InIt2,
    class _OutIt> inline
    _OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
        _InIt2 _First2, _InIt2 _Last2,
        _OutIt _Dest)
    {    // copy merging ranges, both using operator<
    for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
        if (_DEBUG_LT(*_First2, *_First1))
            {    // merge first
            *_Dest = _Move(*_First2);
            ++_First2;
            }
        else
            {    // merge second
            *_Dest = _Move(*_First1);
            ++_First1;
            }

    _Dest = _Move(_First1, _Last1, _Dest);    // copy any tail
    return (_Move(_First2, _Last2, _Dest));
    }

Edited by author 17.12.2010 14:20