Submission #525343

#	Time	Username	Problem	Language	Result	Execution time	Memory
525343		ksu2009en	Table Tennis (info1cup20_tabletennis)	C++14	43 / 100	3082 ms	4432 KiB

tabletennis

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll>a;

set<ll>st;

ll n, k;

bool put(ll l, ll r, ll cnt, ll left, vector<ll>deleted){
    if(left < 0 || l >= n + k || r < 0 || l > r || !st.empty())
        return false;

    //cout << l << ' ' << r << ' ' << cnt << ' ' << left << endl;

    while(l < r){
        if(a[l] + a[r] != cnt){
            if(a[l] + a[r] > cnt){
               vector<ll>b = deleted;
               vector<ll>c = deleted;
                b.push_back(r);
                c.push_back(l);
                c.push_back(r);
               return put(l, r - 1, cnt, left - 1, b) || put(l + 1, r - 1, cnt, left - 2, c);
            }
            else{
                vector<ll>b = deleted;
                vector<ll>c = deleted;
                b.push_back(l);
                c.push_back(l);
                c.push_back(r);
                return put(l + 1, r, cnt, left - 1, b)|| put(l + 1, r - 1, cnt, left - 2, c);
            }
        }
        l++, r--;
    }
    if(deleted.size() == 2){
        for(auto i: deleted)
            st.insert(i);
        return true;
    }

    return false;
}
int main(){
    cin >> n >> k;

    a.resize(n + k);

    for(int i = 0; i < n + k; i++)
        cin >> a[i];

    ll sum = 0;
    for(auto i: a)
        sum += i;

    sort(a.begin(), a.end());

    if(n + k <= 18){
        for(int mask = 0; mask < (1 << (n + k)); mask++){
            ll cnt = 0, mn = 1e9, mx = -1, sum2 = sum;

            map<ll, ll>mp;

            for(int j = 0; j < n + k; j++){
                if((mask >> j) % 2 != 0){
                    //cout << a[j] << ' ';
                    cnt++;
                    sum2 -= a[j];
                }
                else{
                    mn = min(mn, a[j]);
                    mx = max(mx, a[j]);

                    mp[a[j]]++;
                }
            }
           // cout << endl;

            if(cnt != k)
                continue;

            if(sum2 % (n / 2) != 0)
                continue;


            ll bl = sum2 / (n / 2);
            //cout << "Look: " << sum2 << ' ' << bl << endl;

            bool ok = false;

            for(int j = 0; j < n + k; j++){
                if((mask >> j )% 2 != 0)
                    bl = bl;
                else{
                    if(mp[bl - a[j]] <= 0)
                        ok = true;
                    mp[bl - a[j]]--;
                }
            }

            if(ok)
                continue;

            for(int j = 0; j < n + k; j++){
                if((mask >> j) % 2 != 0)
                    bl = bl;
                else
                    cout << a[j] << ' ';
            }
            cout << endl;
            return 0;
        }
    }


    if(k > 1){
        for(int l = 0; l < n + k; l++){
            for(int r = n + k - 1; r >= 0; r--){
                if(l + (n + k - 1 - r) > k)
                    break;

                vector<ll>b;

                for(int j = 0; j < l; j++)
                    b.push_back(j);
                for(int j = r + 1; j < n + k; j++)
                    b.push_back(j);

                if(put(l, r, a[l] + a[r], k - l - (n + k - 1 - r), b)){
                    for(int i = 0; i < n + k; i++){
                        if(!st.count(i))
                            cout << a[i] << ' ';
                    }
                    cout << endl;

                    return 0;
                }
            }
        }

        return 0;
    }

    for(int i = 0; i < n + 1; i++){
        ll sum2 = sum - a[i];

        ll mn = a[0];
        if(i == 0)
            mn = a[1];

        ll mx = a[n + k - 1];
        if(i == n + k - 1)
            mx = a[n + k - 2];

        ll bl = sum2 / (n / 2);
        if(sum2 % (n / 2) != 0)
            continue;

        if(mn + mx < bl || mx >= bl)
            continue;

        for(int j = 0; j < n + k; j++){
            if(j == i)
                continue;
            cout << a[j] << ' ';
        }
        cout << endl;
        return 0;
    }


    return 0;
}

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