結果
問題 | No.332 数列をプレゼントに |
ユーザー |
|
提出日時 | 2015-12-25 00:38:00 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 391 ms / 2,000 ms |
コード長 | 1,938 bytes |
コンパイル時間 | 2,215 ms |
コンパイル使用メモリ | 192,448 KB |
実行使用メモリ | 64,256 KB |
最終ジャッジ日時 | 2024-12-24 07:26:00 |
合計ジャッジ時間 | 6,540 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define GET_MACRO(a, b, c, NAME, ...) NAME#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)#define rep2(i, a) rep3 (i, 0, a)#define rep3(i, a, b) for (int i = (a); i < (b); i++)#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)#define repr2(i, a) repr3 (i, 0, a)#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }using ll = long long;const int N = 50505;int main() {ll n, X;cin >> n >> X;vector<ll> a(n);rep (i, n) cin >> a[i];vector<pair<ll, ll>> ai(n);rep (i, n) ai[i] = {a[i], i};sort(ai.begin(), ai.end());rep (i, n) a[i] = ai[i].first;vector<ll> x, y;rep (i, n) {if (a[i] < N) {x.push_back(a[i]);} else {y.push_back(a[i]);}}int m = x.size();vector<set<ll>> dp(m + 1);vector<map<ll, int>> pre(m + 1);dp[0].insert(0);pre[0][0] = -1;rep (i, m) {for (auto u : dp[i]) {if (!dp[i + 1].count(u)) {dp[i + 1].insert(u);pre[i + 1][u] = u;}if (!dp[i + 1].count(u + x[i])) {dp[i + 1].insert(u + x[i]);pre[i + 1][u + x[i]] = u;}}}map<ll, string> mp;rep (i, 1 << y.size()) {ll sum = 0;string s;rep (j, y.size()) {if (i & 1 << j) {sum += y[j];s += "o";} else {s += "x";}}mp[sum] = s;}for (auto u : dp[m]) {if (mp.count(X - u)) {string ans;int curr = u;int i = m;while (i > 0) {int next = pre[i][curr];if (next < curr) {ans = "o" + ans;} else {ans = "x" + ans;}curr = next;i--;}ans += mp[X - u];string ans2 = ans;rep (i, n) ans2[ai[i].second] = ans[i];cout << ans2 << endl;return 0;}}cout << "No" << endl;return 0;}