Submission #525085

#	Time	Username	Problem	Language	Result	Execution time	Memory
525085		dron_rp	Table Tennis (info1cup20_tabletennis)	C++14	11 / 100	3081 ms	8440 KiB

tabletennis

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

using ll = long long;

ll n, k;
vector<ll> a, ans;
/*

map<pair<ll, ll>, bool> dp;


bool check(ll sum, ll items, ll W, vector<bool>&visited){
    if (sum == W/2 && items == n/2){
        return true;;
    }
    if (dp.count({sum, items})) return dp[{sum, items}];
    dp[{sum, items}] = false;

}
*/



bool good(vector<ll>v){
    sort(v.begin(), v.end());
    ll sum1 = 0, sum2 = 0;
    for (int i = 0; i<n/2; i+=2){
        sum1 += a[i]+a[n-1-i];
        sum2 += a[i+1]+a[n-2-i];
    }
    return sum1 == sum2;
}

vector<ll> transform(vector<bool>&visited){
    vector<ll> v(n);
    int idx = 0;
    for (int i = 0; i<n+k; i++){
        if (visited[i]){
            //cout << i << "\n";
            v[idx++] = a[i];
        }
    }
    return v;
}

void solve(vector<bool>&visited, int cnt){
    if (cnt == k-1){
        vector<ll> b = transform(visited);
        if (good(b)){
            ans = b;
        }
        return;
    }
    for (int i = 0; i<n+k; i++){
        if (visited[i]){
            visited[i] = false;
            solve(visited, cnt+1);
            visited[i] = true;
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   
    


    cin >> n >> k;
    //cerr << n << " " << k << "\n";
    a.resize(n+k);
    for (auto& i : a) cin >> i;
    /*
    vector<ll> v = a;
    vector<bool> visited(n+k, true);
    solve(visited, 0);
    for (auto& i : ans) cout << i << " ";
    */
    
    //vector<bool> visited(n+k, true);
    if ((n/2)%2 == 0){
        for (int i = 0; i<n+k; i++){
            int l = 0, r = n+k-1;
            ll sum1 = 0, sum2 = 0;
            bool turno = true;
            set<ll> res;
            while (l<r){
                if (l == i) l++;
                if (r == i) r--;
                if (turno){
                    sum1 += a[l]+a[r];
                    turno = false;
                }
                else{
                    sum2 += a[l]+a[r];
                    turno = true;
                }
                res.insert(a[l]);
                res.insert(a[r]);
                l++; r--;
            }
            if (sum1 == sum2){
                for (auto& c : res){
                    cout << c << " ";
                }
                cout << "\n";
                return 0;
            }
        }
    } else{
        for (int i = 0; i<n+k; i++){
            int l = 0, r = n+k-1;
            ll sum1 = 0, sum2 = 0;
            bool turno = true;
            set<ll> res;
            pair<ll, ll> last = {0, 0};
            //cout <<i << "\n";
            while (l<r){
                if (l == i) l++;
                if (r == i) r--;
                //cout << l << " " << r << "\n";
                if (turno){
                    sum1 += a[l]+a[r];
                    turno = false;
                }
                else{
                    sum2 += a[l]+a[r];
                    turno = true;
                }
                res.insert(a[l]);
                res.insert(a[r]);
                last = {a[l], a[r]};
                l++; r--;
            }
            //cerr << i << " ";
            
            sum1 -= last.second;
            sum2 += last.second;
            //cerr << sum1 << " " << sum2 << "\n";
            
            if (sum1 == sum2){
                for (auto& c : res){
                    cout << c << " ";
                }
                cout << "\n";
                return 0;
                //return 0;
            }   
        }
    }
    
    
    
    
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 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