oj.uz

Submission #517048

# Submission time Handle Problem Language Result Execution time Memory
517048 2022-01-22T12:43:15 Z Be_dos Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 633 ms 484128 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

int32_t get_matches(int32_t n, int32_t* arr1, int32_t* arr2, int32_t max_missed) {
    int32_t ans = 0;
    int32_t ptr1 = 0, ptr2 = 0;
    int32_t missed = 0;
    while(ptr1 < n && ptr2 < n) {
        if(arr1[ptr1] == arr2[ptr2]) {
            ans++;
            ptr1++;
            ptr2++;
        } else {
            missed++;
            if(missed > max_missed)
                return ans;

            if(arr1[ptr1] < arr2[ptr2])
                ptr1++;
            else
                ptr2++;
        }
    }
    return ans;
}

int main() {
    int32_t n, k;
    std::cin >> n >> k;
    n += k;

    int32_t* arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    int32_t** per_start = new int32_t*[k + 1];
    for(int32_t i = 0; i <= k; i++) {
        per_start[i] = new int32_t[n];
        for(int32_t j = 0; j < n; j++)
            per_start[i][j] = arr[j] - arr[i];
    }
    int32_t** per_end = new int32_t*[k + 1];
    for(int32_t i = 0; i <= k; i++) {
        per_end[i] = new int32_t[n];
        for(int32_t j = 0; j < n; j++)
            per_end[i][j] = arr[n - i - 1] - arr[j];
        std::reverse(per_end[i], per_end[i] + n);
    }

    for(int32_t i = 0; i <= k; i++)
        for(int32_t j = 0;j <= k; j++) {
            int32_t matches = get_matches(n, per_start[i], per_end[j], 2 * k);
            if(matches >= n - k) {
                int32_t true_sum = arr[i] + arr[n - j - 1];
                std::map<int32_t, int32_t> freq;
                for(int32_t p = 0; p < n; p++)
                    freq[arr[p]]++;

                std::vector<int32_t> ans;
                for(int32_t p = 0; p < n; p++)
                    if(arr[p] * 2 < true_sum && freq[true_sum - arr[p]] > 0) {
                        ans.push_back(arr[p]);
                        ans.push_back(true_sum - arr[p]);
                        freq[true_sum - arr[p]]--;
                    } else if(arr[p] * 2 == true_sum && freq[true_sum - arr[p]] > 1) {
                        ans.push_back(arr[p]);
                        ans.push_back(true_sum - arr[p]);
                        freq[true_sum - arr[p]]-=2;
                    }

                ans.resize(n - k);
                std::sort(ans.begin(), ans.end());
                for(int32_t p = 0; p < n - k; p++)
                    std::cout << ans[p] << " ";
                return 0;
            }
        }
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2008 KB Output is correct
2 Correct 125 ms 12396 KB Output is correct
3 Correct 114 ms 12400 KB Output is correct
4 Correct 114 ms 12364 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 13568 KB Output is correct
2 Correct 113 ms 13628 KB Output is correct
3 Correct 124 ms 13644 KB Output is correct
4 Correct 117 ms 13604 KB Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 204 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 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 125 ms 34760 KB Output is correct
3 Correct 129 ms 34792 KB Output is correct
4 Correct 124 ms 34848 KB Output is correct
5 Correct 130 ms 34932 KB Output is correct
6 Correct 128 ms 34796 KB Output is correct
7 Correct 125 ms 34744 KB Output is correct
8 Correct 127 ms 34912 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 633 ms 482608 KB Output is correct
3 Correct 352 ms 484028 KB Output is correct
4 Correct 448 ms 484008 KB Output is correct
5 Correct 338 ms 484004 KB Output is correct
6 Correct 352 ms 484128 KB Output is correct
7 Correct 539 ms 484040 KB Output is correct
8 Correct 396 ms 484036 KB Output is correct