제출 #1141712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141712		otesunki	시간이 돈 (balkan11_timeismoney)	C++20	컴파일 에러	0 ms	0 KiB

timeismoney

#include <iostream>
#include <vector>
#include <tuple>

int N, M;
std::vector<std::tuple<int, int>> chosen;
std::vector<std::tuple<int, int, int, int>> edges;
std::vector<int> reduction;

/*
template<class ForwardIt, class UnaryPred>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPred p) {
  for (ForwardIt i = first; ++i != last;)
    if (!p(*i))
      *first++ = std::move(*i);
  return first;
}
*/

template<class InputIt, class UnaryPred>
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPred p) {
    for (; first != last; ++first)
        if (p(*first))
            return first;
 
    return last;
}

template<class ForwardIt, class UnaryPred>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPred p) {
    first = find_if(first, last, p);
    if (first != last)
        for (ForwardIt i = first; ++i != last;)
            if (!p(*i))
                *first++ = std::move(*i);
    return first;
}

int main(void) {
  std::cin >> N >> M;
  reduction.resize(N);
  for (int i = 0; i < N; ++i) {
    reduction[i] = i;
  }
  for (int i = 0; i < M; ++i) {
    int a, b, t, c;

    std::cin >> a >> b >> t >> c;
    edges.push_back({a, b, t, c});
  }
  int time = 0, cost = 0;
  for (;;) {
    int mintime = -1, mincost = -1, mina = -1, minb = -1;
/*
    std::cout << "    time=" << time << "\n";
    std::cout << "    cost=" << cost << "\n";
    for (int i = 0; i < edges.size(); ++i) {
      std::cout << std::get<0>(edges[i]) << " [" << reduction[std::get<0>(edges[i])] << "] -> "
                << std::get<1>(edges[i]) << " [" << reduction[std::get<1>(edges[i])] << "] (t="
                << std::get<2>(edges[i]) << " | c=" << std::get<3>(edges[i]) << ")\n";
    }
*/
    for (int i = 0; i < edges.size(); ++i) {
      int thistime = (std::get<2>(edges[i]) + time);
      int thiscost = (std::get<3>(edges[i]) + cost);
/*
      std::cout << "thistime=" << thistime << "\n";
      std::cout << "thiscost=" << thiscost << "\n";
      std::cout << "mintime=" << mintime << "\n";
      std::cout << "mincost=" << mincost << "\n";
*/
      if ((thistime * thiscost < mintime * mincost) || (mina == -1)) {
        mintime = thistime;
        mincost = thiscost;
        mina = std::get<0>(edges[i]);
        minb = std::get<1>(edges[i]);
      }
    }
    time = mintime;
    cost = mincost;
    int minredi = 201, maxredi = 0;
    chosen.push_back({mina, minb});
    int reductionminb = reduction[minb];
    int reductionmina = reduction[mina];
/*
    std::cout << "merge " << reductionmina << " with " << reductionminb << "\n";
*/
    for (int i = 0; i < N; ++i) {
      if (reduction[i] == reductionminb) {
        reduction[i] = reductionmina;
      }
      if (reduction[i] < minredi) {
        minredi = reduction[i];
      }
      if (reduction[i] > maxredi) {
        maxredi = reduction[i];
      }
    }
    if (minredi == maxredi) {
      break;
    }
    auto it = remove_if(std::begin(edges), std::end(edges), [](auto edge) {
/*
      std::cout << "  compare " << reduction[std::get<0>(edge)] << " & " << reduction[std::get<1>(edge)] << "\n";
*/
      return reduction[std::get<0>(edge)] == reduction[std::get<1>(edge)];
    });
    edges.erase(it, std::end(edges));
  }

  std::cout << time << " " << cost << "\n";
  for (auto edge : chosen) {
    std::cout << std::get<0>(edge) << " " << std::get<1>(edge) << "\n";
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:102:24: error: call of overloaded 'remove_if(std::vector<std::tuple<int, int, int, int> >::iterator, std::vector<std::tuple<int, int, int, int> >::iterator, main()::<lambda(auto:11)>)' is ambiguous
  102 |     auto it = remove_if(std::begin(edges), std::end(edges), [](auto edge) {
      |               ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  103 | /*
      | ~~                      
  104 |       std::cout << "  compare " << reduction[std::get<0>(edge)] << " & " << reduction[std::get<1>(edge)] << "\n";
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  105 | */
      | ~~                      
  106 |       return reduction[std::get<0>(edge)] == reduction[std::get<1>(edge)];
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  107 |     });
      |     ~~                  
timeismoney.cpp:30:11: note: candidate: 'ForwardIt remove_if(ForwardIt, ForwardIt, UnaryPred) [with ForwardIt = __gnu_cxx::__normal_iterator<std::tuple<int, int, int, int>*, std::vector<std::tuple<int, int, int, int> > >; UnaryPred = main()::<lambda(auto:11)>]'
   30 | ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPred p) {
      |           ^~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from timeismoney.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:884:5: note: candidate: 'constexpr _FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = __gnu_cxx::__normal_iterator<std::tuple<int, int, int, int>*, std::vector<std::tuple<int, int, int, int> > >; _Predicate = main()::<lambda(auto:11)>]'
  884 |     remove_if(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~