oj.uz

Submission #718293

# Submission time Handle Problem Language Result Execution time Memory
718293 2023-04-03T19:51:03 Z haxorman Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 494 ms 288060 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mxN = 2e5 + 7;

int arr[mxN];

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, k;
    cin >> n >> k;
    
    bitset<2000000001> in;
    for (int i = 0; i < n + k; ++i) {
        cin >> arr[i];
        in[arr[i]] = true;
    }

    if (n <= 4 * k) {
        for (int i = 0; i < n + k; ++i) {
            cin >> arr[i];
            in[arr[i]] = true;
        }
        
        assert(n >= 2);
        for (int i = 0; i < k + 2;  ++i) {
            for (int j = n + k - 1; j >= n - 1 && j > i; --j) {
                int sum = arr[i] + arr[j];

                vector<int> nums;
                for (int l = 0; l < n + k; ++l) {
                    if (sum - arr[l] >= 0 && in[sum - arr[l]]) {
                        nums.push_back(arr[l]);
                    }
                }

                if (nums.size() >= n) {
                    for (int l = 0; l < n; ++l) {
                        cout << nums[l] << ' ';
                    }
                    cout << "\n";
                    exit(0);
                }
            }
        }
    }
    else {
        map<int,int> freq;
        for (int i = 0; i < 2 * k + 2;  ++i) {
            for (int j = n + k - 1; j >= n - k - 1; --j) {
                int sum = arr[i] + arr[j];
                freq[sum]++;
            }
        }

        for (auto p : freq) {
            if (p.second >= k) {
                int sum = p.first;
                vector<int> nums;
                for (int l = 0; l < n + k; ++l) {
                    if (sum - arr[l] >= 0 && in[sum - arr[l]]) {
                        nums.push_back(arr[l]);
                    }
                }

                if (nums.size() >= n) {
                    for (int l = 0; l < n; ++l) {
                        cout << nums[l] << ' ';
                    }
                    cout << "\n";
                    exit(0);
                }
            }
        }
    }
    
    assert(false);
}
// 1 2 1 2 3

Compilation message

tabletennis.cpp: In function 'int32_t main()':
tabletennis.cpp:40:33: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   40 |                 if (nums.size() >= n) {
      |                     ~~~~~~~~~~~~^~~~
tabletennis.cpp:69:33: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   69 |                 if (nums.size() >= n) {
      |                     ~~~~~~~~~~~~^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 244936 KB Output is correct
2 Correct 118 ms 244864 KB Output is correct
3 Correct 120 ms 244900 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 245632 KB Output is correct
2 Correct 159 ms 248864 KB Output is correct
3 Correct 159 ms 248904 KB Output is correct
4 Correct 159 ms 248976 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 248832 KB Output is correct
2 Correct 155 ms 248924 KB Output is correct
3 Correct 162 ms 248968 KB Output is correct
4 Correct 159 ms 248896 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 244876 KB Output is correct
2 Correct 123 ms 244804 KB Output is correct
3 Correct 115 ms 244860 KB Output is correct
4 Correct 131 ms 244812 KB Output is correct
5 Correct 118 ms 244844 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 244880 KB Output is correct
2 Correct 119 ms 244812 KB Output is correct
3 Correct 130 ms 244916 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 244940 KB Output is correct
2 Correct 116 ms 244916 KB Output is correct
3 Correct 123 ms 245000 KB Output is correct
4 Correct 131 ms 244940 KB Output is correct
5 Correct 119 ms 244964 KB Output is correct
6 Correct 118 ms 244908 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 244872 KB Output is correct
2 Correct 163 ms 248960 KB Output is correct
3 Correct 157 ms 248844 KB Output is correct
4 Correct 176 ms 248940 KB Output is correct
5 Correct 169 ms 248820 KB Output is correct
6 Correct 147 ms 250856 KB Output is correct
7 Correct 183 ms 248896 KB Output is correct
8 Correct 178 ms 248868 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 244836 KB Output is correct
2 Correct 438 ms 285736 KB Output is correct
3 Correct 370 ms 288060 KB Output is correct
4 Correct 315 ms 282664 KB Output is correct
5 Correct 494 ms 258180 KB Output is correct
6 Correct 182 ms 251200 KB Output is correct
7 Correct 306 ms 279704 KB Output is correct
8 Correct 301 ms 282728 KB Output is correct