oj.uz

답안 #993497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993497 2024-06-05T20:09:28 Z DBuchBof A Plus B (IOI23_aplusb) C++17
0 / 100
 1 ms 344 KB 
#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-1) 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
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -