oj.uz

Submission #524394

# Submission time Handle Problem Language Result Execution time Memory
524394 2022-02-09T07:05:50 Z mateigg4 Table Tennis (info1cup20_tabletennis) C++14
87 / 100
 3000 ms 4172 KB 
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#define nmax 160000
#pragma GCC optimize("Ofast")
#define int long long
 
using namespace std;
 
int v[nmax + 1];
pair<int, int> sol[nmax + 1];
map<int, int> f;
 
signed main()
{
    int n, k, i, j, x, y, st, dr, s, p;
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (i = 1; i <= n + k; i++)
        cin >> v[i];
    sort(v + 1, v + n + k + 1);
    for (x = 0; x < 2 * k; x++)
        for (y = n + k + 1; y > n - k; y--)
        {
            if (x + n + k - y <= k && f[v[x + 1] + v[y - 1]] == 0)
            {
                s = v[x + 1] + v[y - 1];
                // cout << s << endl;
                p = 0;
                st = x + 1, dr = y - 1;
                for (i = st; i <= dr; i++)
                {
                    while (dr > i && v[i] + v[dr] > s)
                        dr--;
                    if (v[i] + v[dr] == s && p < n / 2)
                    {
                        sol[p++] = {v[i], v[dr]};
                        // cout << v[i] << " " << v[dr] << endl;
                    }
                }
                if (p >= n / 2)
                {
                    for (i = 0; i < n / 2; i++)
                        cout << sol[i].first << " ";
                    for (i = n / 2 - 1; i >= 0; i--)
                        cout << sol[i].second << " ";
                    return 0;
                }
                f[s]++;
            }
            else
                break;
        }
    return 0;
}

Compilation message

tabletennis.cpp: In function 'int main()':
tabletennis.cpp:17:18: warning: unused variable 'j' [-Wunused-variable]
   17 |     int n, k, i, j, x, y, st, dr, s, p;
      |                  ^

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 28 ms 4092 KB Output is correct
3 Correct 27 ms 4036 KB Output is correct
4 Correct 28 ms 4080 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4136 KB Output is correct
2 Correct 26 ms 4172 KB Output is correct
3 Correct 29 ms 4140 KB Output is correct
4 Correct 28 ms 4128 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 157 ms 4172 KB Output is correct
3 Correct 34 ms 4164 KB Output is correct
4 Correct 55 ms 4052 KB Output is correct
5 Correct 29 ms 4132 KB Output is correct
6 Correct 35 ms 4132 KB Output is correct
7 Correct 50 ms 4056 KB Output is correct
8 Correct 31 ms 4048 KB Output is correct

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 3078 ms 1712 KB Time limit exceeded
3 Halted 0 ms 0 KB -