Submission

P-PP-PP--P

Score: 60

User: NJTYTYTY

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-07 06:50:19

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <cmath>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> a(n);
    int total = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        total += a[i];
    }
    
    // กำหนดจำนวนสมาชิกในทีมที่ 1
    int m = (n % 2 == 0) ? n/2 : (n-1)/2;
    
    // หาค่าสูงสุดของผลรวมบวกและต่ำสุดของผลรวมน้อย (สำหรับใช้ในการ shift ค่า sum)
    int sumPos = 0, sumNeg = 0;
    for(int i = 0; i < n; i++){
        if(a[i] >= 0)
            sumPos += a[i];
        else
            sumNeg += a[i];
    }
    int offset = -sumNeg; // ผลรวมจริง = index - offset
    int range = sumPos - sumNeg + 1; // พื้นที่ของผลรวมที่เป็นไปได้

    // dp[count][s] = สามารถเลือก count ตัวที่มีผลรวม = (s - offset) ได้หรือไม่
    vector<vector<bool>> dp(m+1, vector<bool>(range, false));
    // parent[count][s] เก็บค่า s ของ state ก่อนหน้า
    vector<vector<int>> parent(m+1, vector<int>(range, -1));
    // used[count][s] เก็บ index ของตัวเลขที่ถูกเลือกใน state นี้
    vector<vector<int>> used(m+1, vector<int>(range, -1));
    
    // เริ่มต้น: เลือก 0 ตัวแล้วผลรวม 0 (ซึ่งอยู่ที่ index offset)
    dp[0][offset] = true;
    
    // สำหรับแต่ละ element (ดำเนินการตามลำดับของ input)
    for(int i = 0; i < n; i++){
        // ทำการ update จากจำนวนที่เลือกในตอนนี้โดยย้อนกลับ (เพื่อไม่ให้ใช้ element ซ้ำใน iteration เดียวกัน)
        for(int count = m - 1; count >= 0; count--){
            for(int s = 0; s < range; s++){
                if(dp[count][s]){
                    int ns = s + a[i];
                    if(ns < 0 || ns >= range) continue;
                    if(!dp[count+1][ns]){
                        dp[count+1][ns] = true;
                        parent[count+1][ns] = s;
                        used[count+1][ns] = i;
                    }
                }
            }
        }
    }
    
    // ค้นหาผลรวม s (ใน state dp[m]) ที่ทำให้ |2*s - total| มีค่าน้อยที่สุด
    int bestSumIndex = -1;
    int bestDiff = INT_MAX;
    for(int s = 0; s < range; s++){
        if(dp[m][s]){
            int curSum = s - offset; // ผลรวมที่ได้
            int diff = abs(total - 2 * curSum);
            if(diff < bestDiff){
                bestDiff = diff;
                bestSumIndex = s;
            }
        }
    }
    
    // ถ้าไม่พบ (ควรจะพบเสมอ) ก็ออกจากโปรแกรม
    if(bestSumIndex == -1){
        cout << "No solution\n";
        return 0;
    }
    
    // สร้าง subset สำหรับทีมที่ 1 โดยย้อนกลับจาก dp (จะได้ index ในลำดับย้อนกลับ)
    vector<int> team1Indices;
    int curCount = m;
    int curS = bestSumIndex;
    while(curCount > 0){
        int idx = used[curCount][curS];
        team1Indices.push_back(idx);
        int prevS = parent[curCount][curS];
        curS = prevS;
        curCount--;
    }
    // เรียง index ของทีมที่ 1 ตามลำดับต้นฉบับ (เพิ่มขึ้น)
    sort(team1Indices.begin(), team1Indices.end());
    
    // สร้างทีมที่ 2 โดยเลือกสมาชิกที่ไม่อยู่ในทีมที่ 1
    vector<int> team2Indices;
    vector<bool> inTeam1(n, false);
    for (int idx : team1Indices)
        inTeam1[idx] = true;
    for(int i = 0; i < n; i++){
        if(!inTeam1[i])
            team2Indices.push_back(i);
    }
    
    // แสดงผล ทีมที่ 1
    for (int idx : team1Indices)
        cout << a[idx] << " ";
    cout << "\n";
    // แสดงผล ทีมที่ 2
    for (int idx : team2Indices)
        cout << a[idx] << " ";
    cout << "\n";
    
    return 0;
}