Submission #839958

#	Time	Username	Problem	Language	Result	Execution time	Memory
839958		SorahISA	A Plus B (IOI23_aplusb)	C++17	100 / 100	88 ms	12800 KiB

aplusb

#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

vector<int> smallest_sums(int N, vector<int> A, vector<int> B) {
    prior<tuple<int, int, int>> pq;
    pq.ee(A[0] + B[0], 0, 0);
    
    vector<int> ans;
    set<pii> st;
    for (int i = 0; i < N; ++i) {
        auto [val, pos_a, pos_b] = pq.top(); pq.pop();
        ans.eb(val);
        if (pos_a + 1 < N and !st.count({pos_a + 1, pos_b})) {
            pq.ee(A[pos_a + 1] + B[pos_b], pos_a + 1, pos_b);
            st.ee(pos_a + 1, pos_b);
        }
        if (pos_b + 1 < N and !st.count({pos_a, pos_b + 1})) {
            pq.ee(A[pos_a] + B[pos_b + 1], pos_a, pos_b + 1);
            st.ee(pos_a, pos_b + 1);
        }
    }
    
    return ans;
}

#else

#include "aplusb.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

#endif

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