oj.uz

Submission #208507

# Submission time Handle Problem Language Result Execution time Memory
208507 2020-03-11T11:19:29 Z tamionv Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 878 ms 2808 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using cd = complex<double>;

auto mt = mt19937(12312);

int main(){
    int n, k;
    cin >> n >> k;

    vector<int> v(n + k);
    for(auto& x : v){
        cin >> x;
        assert(1 <= x && x <= 1e9);
    }

    vector<int> l;
    int the_sum = 0;
    l.reserve(n / 2);

    auto try_sum = [&](int s){
        int i = 0, j = n + k - 1;
        l.clear();
        the_sum = s;

        while(i < j && 2 * l.size() < n){
            if(v[i] + v[j] < s) ++i;
            else if(v[i] + v[j] > s) --j;
            else{
                l.push_back(v[i]);
                ++i, --j;
            }
        }

        if(2 * l.size() < n) l.clear();
    };

    do{
        int i = uniform_int_distribution<int>(0, n + k-1)(mt);
        for(int j = n - 1 - i; l.empty() && j <= n - 1 - i + 2 * k; ++j) {
            if(j < 0) continue;
            if(j >= n + k) break;
            try_sum(v[i] + v[j]);
        }
    } while(l.empty());

    for(auto x : l)
        cout << x << ' ';
    reverse(begin(l), end(l));
    for(auto x : l)
        cout << the_sum - x << ' ';

    return 0;
}

Compilation message

tabletennis.cpp: In lambda function:
tabletennis.cpp:28:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < j && 2 * l.size() < n){
                        ~~~~~~~~~~~~~^~~
tabletennis.cpp:37:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(2 * l.size() < n) l.clear();
            ~~~~~~~~~~~~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 640 KB Output is correct
2 Correct 119 ms 2756 KB Output is correct
3 Correct 110 ms 2680 KB Output is correct
4 Correct 115 ms 2680 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2680 KB Output is correct
2 Correct 112 ms 2792 KB Output is correct
3 Correct 113 ms 2808 KB Output is correct
4 Correct 110 ms 2680 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 150 ms 2808 KB Output is correct
3 Correct 115 ms 2808 KB Output is correct
4 Correct 113 ms 2684 KB Output is correct
5 Correct 114 ms 2680 KB Output is correct
6 Correct 113 ms 2680 KB Output is correct
7 Correct 113 ms 2680 KB Output is correct
8 Correct 116 ms 2680 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 878 ms 2808 KB Output is correct
3 Correct 116 ms 2680 KB Output is correct
4 Correct 280 ms 2628 KB Output is correct
5 Correct 169 ms 2680 KB Output is correct
6 Correct 115 ms 2680 KB Output is correct
7 Correct 284 ms 2808 KB Output is correct
8 Correct 285 ms 2808 KB Output is correct