oj.uz

답안 #525085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525085 2022-02-10T16:23:49 Z dron_rp Table Tennis (info1cup20_tabletennis) C++14
11 / 100
 3000 ms 8440 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 412 ms 416 KB Output is correct
3 Correct 371 ms 428 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3081 ms 1380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3080 ms 8440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 332 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -