oj.uz

Submission #769531

# Submission time Handle Problem Language Result Execution time Memory
769531 2023-06-29T18:16:50 Z borisAngelov Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 95 ms 4564 KB 
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int maxn = 200005;

int n, k;

int a[maxn];

vector<int> solution;

bool check(int i, int j)
{
    solution.clear();

    int lp = i;
    int rp = j;

    int sum = a[lp] + a[rp];

    solution.push_back(a[lp]);
    solution.push_back(a[rp]);

    ++lp;
    --rp;

    while (rp - lp >= 1 && solution.size() <= n - 1)
    {
        if (rp - lp + 1 + solution.size() <= n - 1)
        {
            return false;
        }

        if (a[lp] + a[rp] == sum)
        {
            solution.push_back(a[lp]);
            solution.push_back(a[rp]);

            ++lp;
            --rp;

            continue;
        }

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

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

    return solution.size() == n;
}

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

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

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

    for (int i = 1; i <= n; ++i)
    {
        for (int j = n + k; j >= n + i - 1; --j)
        {
            if (check(i, j) == true)
            {
                sort(solution.begin(), solution.end());

                for (auto idx : solution)
                {
                    cout << idx << ' ';
                }

                cout << endl;

                return 0;
            }
        }
    }

    return 0;
}

Compilation message

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

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 740 KB Output is correct
2 Correct 58 ms 4544 KB Output is correct
3 Correct 57 ms 4428 KB Output is correct
4 Correct 57 ms 4416 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2964 KB Output is correct
2 Correct 57 ms 4544 KB Output is correct
3 Correct 58 ms 4544 KB Output is correct
4 Correct 59 ms 4464 KB Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct

Subtask #6
14.0 / 14.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 57 ms 4564 KB Output is correct
3 Correct 57 ms 4472 KB Output is correct
4 Correct 62 ms 4460 KB Output is correct
5 Correct 56 ms 4448 KB Output is correct
6 Correct 58 ms 4496 KB Output is correct
7 Correct 56 ms 4552 KB Output is correct
8 Correct 56 ms 4456 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 76 ms 4496 KB Output is correct
3 Correct 63 ms 4500 KB Output is correct
4 Correct 74 ms 4488 KB Output is correct
5 Correct 73 ms 4400 KB Output is correct
6 Correct 57 ms 4544 KB Output is correct
7 Correct 95 ms 4436 KB Output is correct
8 Correct 56 ms 4404 KB Output is correct