제출 #1132701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132701		sethod	Table Tennis (info1cup20_tabletennis)	C++20	20 / 100	3095 ms	3180 KiB

tabletennis

#include <bits/stdc++.h>
using namespace std;


int main(){
    int n, k;
    cin >> n >> k;
    int arr[n + k];
    for(int i = 0; i < n + k; i++){
        cin >> arr[i];
    }
    int l = 0, r = n + k - 1;
    bool found = 0;
    queue<pair<int, int>> q;
    vector <int> ans;
    q.push({l, r});
    map<pair<int,int>, int> m;
    while(!q.empty() && !found){
        
        // cerr << found << " ";
        vector<int> tmp;
        int l1 = q.front().first;
        int r1 = q.front().second;
        int l2 = q.front().first;
        int r2 = q.front().second;
        if(m[{l2, r2}] != 0){
            continue;
        }
        int sum = arr[l1] + arr[r1];
        tmp.push_back(arr[l1]);
        tmp.push_back(arr[r1]);
        q.pop();
        l1++;
        r1--;
        // cerr << l2 << " " << r2 << " " << sum << " " << endl;
        while(l1 < r1){
            // cerr << arr[l1] << " " << arr[r1] << " " << sum << endl;
            if(arr[l1] + arr[r1] == sum){
                // cerr << arr[l1] << " " << arr[r1] << " " << sum << endl;
                tmp.push_back(arr[l1]);
                tmp.push_back(arr[r1]);
                l1++;
                r1--;
            }
            else if(arr[l1] + arr[r1] < sum) l1++;
            else r1--;
        }
        // cerr << tmp.size() << endl;
        m[{l2, r2}] = tmp.size();
        if(tmp.size() >= n){
            found = true;
            ans.assign(tmp.begin(), tmp.begin() + n);
        }
        else{
            q.push({l2 + 1, r2});
            q.push({l2, r2 - 1});
        }
        // cerr << endl;
    }
    sort(ans.begin(), ans.end());
    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

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