Submission #993499

#	Time	Username	Problem	Language	Result	Execution time	Memory
993499		DBuchBof	A Plus B (IOI23_aplusb)	C++17	100 / 100	37 ms	5956 KiB

aplusb

#include "aplusb.h"
#include <queue>

#define NMAX 100000

int *A, *B;
int sum(int p[2]) {return A[p[0]] + B[p[1]];}
int pair[2*NMAX][2];

struct compareSum {
  bool operator() (int below, int above) {
    return sum(pair[below]) > sum(pair[above]);
  }
};

std::vector<int> smallest_sums(int N, std::vector<int> vectorA, std::vector<int> vectorB) {
  A = vectorA.data();
  B = vectorB.data();
  for (int i = 0; i != N-1; ++i) pair[i][0] = N-1 - i;
  for (int i = N; i != 2*N - 1; ++i) pair[i][1] = i - N+1;

  std::vector<int> result(N);

  std::priority_queue<int, std::vector<int>, compareSum> next;
  next.push(N - 1);

  int idx = 0;
  while (true) {
    int node = next.top();
    next.pop();
    result[idx++] = sum(pair[node]);

    if (idx == N) break;

    if (node < 2 || pair[node - 1][1] == pair[node - 2][1]) next.push(node - 1);
    if (node > 2*N - 4 || pair[node + 1][0] == pair[node + 2][0]) next.push(node + 1);

    ++pair[node][0];
    ++pair[node][1];
  }

  return result;
}

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