結果

問題 No.332 数列をプレゼントに
ユーザー qwewe
提出日時 2025-05-14 13:26:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,609 bytes
コンパイル時間 956 ms
コンパイル使用メモリ 91,204 KB
実行使用メモリ 44,392 KB
最終ジャッジ日時 2025-05-14 13:27:28
合計ジャッジ時間 8,183 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 25 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;

// Function to generate subset sums and corresponding masks for a given list of items.
// Each item in current_half_items_with_orig_idx is a pair (value, original_index).
// The returned map maps a sum to an integer bitmask. The i-th bit of the mask
// is set if the i-th item from current_half_items_with_orig_idx is used.
map<long long, int> get_sums_with_masks(const vector<pair<long long, int>>& current_half_items_with_orig_idx) {
    map<long long, int> res;
    res[0] = 0; // Base case: sum 0 is achieved with an empty set (mask 0)

    // Iterate through each item in this half
    for (int i = 0; i < current_half_items_with_orig_idx.size(); ++i) {
        long long val = current_half_items_with_orig_idx[i].first;
        // int original_index = current_half_items_with_orig_idx[i].second; // Not directly used for mask logic here

        // To avoid issues with modifying the map while iterating, store new sums temporarily
        vector<pair<long long, int>> new_additions;
        for (auto const& [current_sum, current_mask] : res) {
            long long next_sum = current_sum + val;
            int next_mask = current_mask | (1 << i); // Set i-th bit for i-th item of this half
            new_additions.push_back({next_sum, next_mask});
        }
        
        // Add the new sums to the result map.
        // If a sum can be formed in multiple ways, this keeps the one formed by adding the current item
        // to an existing sum that was processed earlier (effectively, first encountered for that sum).
        // Since any solution is fine, this is acceptable.
        for(const auto& p : new_additions) {
            if (res.find(p.first) == res.end()) { 
                 res[p.first] = p.second;
            }
            // Alternate: res[p.first] = p.second; // This would overwrite, taking the "last" way. Any is fine.
        }
    }
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long X;
    cin >> N >> X;

    vector<pair<long long, int>> A_with_indices(N);
    for (int i = 0; i < N; ++i) {
        cin >> A_with_indices[i].first;
        A_with_indices[i].second = i; // Store original index
    }
    
    // If X is larger than the maximum possible sum (100 * 10^9 = 10^11), it's impossible.
    if (X > 100LL * 1000000000LL) {
         cout << "No" << endl;
         return 0;
    }

    string result_str(N, 'x'); // Initialize result string with all 'x'
    bool found = false;

    // Divide A into two halves
    int n1 = N / 2;
    int n2 = N - n1;

    vector<pair<long long, int>> first_half_items;
    for (int i = 0; i < n1; ++i) {
        first_half_items.push_back(A_with_indices[i]);
    }

    vector<pair<long long, int>> second_half_items;
    for (int i = 0; i < n2; ++i) {
        // Items for the second half are A_with_indices[n1], A_with_indices[n1+1], ...
        second_half_items.push_back(A_with_indices[n1 + i]);
    }

    // Generate sums for both halves
    map<long long, int> sums1 = get_sums_with_masks(first_half_items);
    map<long long, int> sums2 = get_sums_with_masks(second_half_items);
    
    // Meet-in-the-middle: combine sums from two halves
    for (auto const& [s1, m1] : sums1) {
        if (s1 > X && X >=0 ) continue; // Optimization: if s1 itself is > X, s1+s2 (s2>=0) will also be.
                                  // (A_i are natural numbers, so sums are non-negative.)
        
        long long target_s2 = X - s1;
        if (sums2.count(target_s2)) { // Check if X-s1 can be formed by the second half
            int m2 = sums2.at(target_s2); // .at() is safer, or sums2[target_s2] if sure it exists
            found = true;
            
            // Reconstruct the path string S
            // Process mask from first half
            for (int i = 0; i < n1; ++i) {
                if ((m1 >> i) & 1) { // If i-th item of first_half_items was used
                    result_str[first_half_items[i].second] = 'o';
                }
            }
            // Process mask from second half
            for (int i = 0; i < n2; ++i) {
                if ((m2 >> i) & 1) { // If i-th item of second_half_items was used
                    result_str[second_half_items[i].second] = 'o';
                }
            }
            break; // Found a solution, exit loop
        }
    }

    if (found) {
        cout << result_str << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}
0