#include #include #include #include #include #include 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 get_sums_with_masks(const vector>& current_half_items_with_orig_idx) { map 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> 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> 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> first_half_items; for (int i = 0; i < n1; ++i) { first_half_items.push_back(A_with_indices[i]); } vector> 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 sums1 = get_sums_with_masks(first_half_items); map 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; }