Submission #632108

#	Time	Username	Problem	Language	Result	Execution time	Memory
632108		boris_mihov	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	76 ms	4720 KiB

tabletennis

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 150000 + 400 + 10;
const int INF  = 1e9;

std::vector <int> solution;
int a[MAXN];
int n, k;

bool trySolution(int lp, int rp)
{
    solution.clear();
    int searchSum = a[lp] + a[rp];
    solution.push_back(a[lp]);
    solution.push_back(a[rp]);
    lp++;
    rp--;

    while (lp <= rp-1 && solution.size() <= n-1)
    {
        if (rp - lp + 1 + solution.size() <= n-1) return false;
        if (a[lp] + a[rp] == searchSum)
        {
            solution.push_back(a[lp]);
            solution.push_back(a[rp]);
            lp++;
            rp--;
            continue;
        }

        if (a[lp] + a[rp] < searchSum)
        {
            lp++;
            continue;
        }   

        if (a[lp] + a[rp] > searchSum)
        {
            rp--;
            continue;
        }   
    }

    return solution.size() == n;
}

void solve()
{
    std::sort(a + 1, a + 1 + n);
    for (int i = 1 ; i <= k + 1 ; ++i)
    {
        for (int j = n + k ; j >= n + i - 1 ; --j)
        {
            if (trySolution(i, j))
            {
                std::sort(solution.begin(), solution.end());
                for (const int &i : solution) std::cout << i << ' ';
                std::cout << '\n';
                return;
            }
        }
    }
}

void read()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n + k ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

Compilation message (stderr)

tabletennis.cpp: In function 'bool trySolution(int, int)':
tabletennis.cpp:24:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     while (lp <= rp-1 && solution.size() <= n-1)
      |                          ~~~~~~~~~~~~~~~~^~~~~~
tabletennis.cpp:26:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         if (rp - lp + 1 + solution.size() <= n-1) return false;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
tabletennis.cpp:49:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |     return solution.size() == n;
      |            ~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 11 / 11
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 9 / 9
• Subtask 6: 14 / 14
• Subtask 7: 15 / 15
• Subtask 8: 13 / 13