제출 #1158033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158033		sunflower	A Plus B (IOI23_aplusb)	C++17	100 / 100	53 ms	2500 KiB

aplusb

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

bool check(int val, const vector <int> &a, const vector <int> &b) {
    int ans = 0, n = SZ(a);
    FOR(i, 0, n - 1) {
        int l = 0, r = n - 1, g, vt = -1;
        while (l <= r) {
            g = (l + r) >> 1;
            if (a[i] + b[g] <= val) vt = g, l = g + 1;
            else r = g - 1;
        }

        if (~vt) ans += vt + 1;

        if (ans >= n) return true;
    }
    return false;
}


/// bug because set l (int) & r (int), g se bi tran so;
vector <int> smallest_sums(int n, vector <int> a, vector <int> b) {
    ll l = 0, r = (int) 2e9 + 7, g, vt = -1;
    while (l <= r) {
        g = (l + r) >> 1;
        if (check(g, a, b)) vt = g, r = g - 1;
        else l = g + 1;
    }

    vector <int> results;
    FOR(i, 0, n - 1) {
        FOR(j, 0, n - 1) {
            if (a[i] + b[j] >= vt) break;
            results.push_back(a[i] + b[j]);
        }
    }

    sort(ALL(results));
    while (SZ(results) < n) results.push_back(vt);

    return results;
}

#ifdef SUN

int main() {
    int n;
    cin >> n;
    vector <int> a(n), b(n);
    FOR(i, 0, n - 1) cin >> a[i];
    FOR(i, 0, n - 1) cin >> b[i];

    vector <int> res = smallest_sums(n, a, b);

    for (int x : res) cout << x << " ";

    return 0;
}
#endif // SUN

/* Discipline - Calm */

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