Submission #991942

#	Time	Username	Problem	Language	Result	Execution time	Memory
991942		jakobrs	A Plus B (IOI23_aplusb)	C++17	100 / 100	80 ms	9792 KiB

aplusb

#include "aplusb.h"

#include <queue>
#include <set>
#include <vector>

std::vector<int> smallest_sums(int N, std::vector<int> A, std::vector<int> B) {
  auto cmp = [&](std::pair<int, int> a, std::pair<int, int> b) {
    auto [a1, a2] = a;
    auto [b1, b2] = b;

    return A[a1] + B[a2] > A[b1] + B[b2];
  };
  auto pq =
      std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                          decltype(cmp)>(cmp);
  pq.push({0, 0});

  auto seen = std::set<std::pair<int, int>>{};

  std::vector<int> results;
  for (int i = 0; i < N; i++) {
  pick:
    auto [a, b] = pq.top();
    pq.pop();
    if (seen.find({a, b}) != seen.end())
      goto pick;
    seen.insert({a, b});
    results.push_back(A[a] + B[b]);
    if (a + 1 < A.size())
      pq.push({a + 1, b});
    if (b + 1 < B.size())
      pq.push({a, b + 1});
  }

  return results;
}

Compilation message (stderr)

aplusb.cpp: In function 'std::vector<int> smallest_sums(int, std::vector<int>, std::vector<int>)':
aplusb.cpp:30:15: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if (a + 1 < A.size())
      |         ~~~~~~^~~~~~~~~~
aplusb.cpp:32:15: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if (b + 1 < B.size())
      |         ~~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40