oj.uz

Submission #954950

# Submission time Handle Problem Language Result Execution time Memory
954950 2024-03-29T00:24:32 Z KasymK A Plus B (IOI23_aplusb) C++17
0 / 100
 1000 ms 444 KB 
#include "aplusb.h"
#include "bits/stdc++.h"
using namespace std;

bool check(int mid, vector<int> a, vector<int> b, int n){
    int cnt = 0;
    for(int &i : a)
        for(int &j : b){
            if(i + j > mid)
                break;
            else
                cnt++;
        }
    return cnt >= n;
}

vector<int> smallest_sums(int N, vector<int> A, vector<int> B){
    vector<int> a = A;
    vector<int> b = B;
    int n = N;
    int l = 0, r = a.back() + b.back();
    int id = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid, a, b, n)){
            id = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    multiset<int> s;
    for(int &i : a)
        for(int &j : b){
            if(i + j > id)
                break;
            else
                s.insert(i + j);
        }
    int cnt = 0;
    vector<int> ans;
    for(int i : s){
        if(cnt == n)
            break;
        cnt++;
        ans.push_back(i);
    }
    return ans;
}

// int main(){
//     int n;
//     cin >> n;
//     vector<int> a(n), b(n);
//     for(int &i : a)
//         cin >> i;
//     for(int &i : b)
//         cin >> i;
//     // a and b is sorted
//     int l = 0, r = a.back() + b.back();
//     int id = 0;
//     while(l <= r){
//         int mid = (l + r) >> 1;
//         if(check(mid, a, b, n)){
//             id = mid;
//             r = mid - 1;
//         }
//         else
//             l = mid + 1;
//     }
//     multiset<int> s;
//     for(int &i : a)
//         for(int &j : b){
//             if(i + j > id)
//                 break;
//             else
//                 s.insert(i + j);
//         }
//     int cnt = 0;
//     for(int i : s){
//         if(cnt == n)
//             break;
//         cnt++;
//         cout << i << " ";
//     }
//     cout << "\n";
//     return 0;
// }

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 1039 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 1039 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 1039 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 1039 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -