#include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef complex P; typedef pair pii; #define REP(i,n) for(ll i=0;i>n>>x; vl a(n); REP(i,n)cin>>a[i]; // ウルトラスーパー考察ターイム // 総積条件が怪しい // ウェイト置くナップサックはX<=1e12で間に合わず // 当然全部殴ろうにも2^100パターン出て無理 // Xは1e12 // A1~ANをソートしたとして、総積が1e100(オーダー)だとしておく // 最悪の場合ANを1e12オーダーとして、次は1e8ぐらい // N=100なのでO(NT)としてTが1e6ぐらいなら間に合う // 最大の重みが1e6のナップサックに落とせれば行けそう // 1e6を超えるAは、(1e6)^18=1e108で、たかだか18個 // -> 最大2^18パターンを保持しておく // -> X-S<=1e6となるようなSだけを取っておく(|S|<=1e6) // -> 残ったAで1e6ナップサック // -> 和を求める // -> あとはこの値を元に復元する // C++なら復元適当でも間に合うでしょw // よく考えたら1e5より大きい数はたかだか20個 // 閾値を10^Aとする // 閾値より大きい数は(10^A)^N=10^100 => N=100/A // 組み合わせ全探索ループは2^N // ナップサックは10^A*100 // ぐーぐるせんせー!に 2^(100/x)-10^(x+2) を計算してもらったところx=4.5ぐらいが最適っぽい // ので閾値は10^4.5=30000 を閾値にしよう // 待って待って // 1e6を100個積んだら1e8になるな // つまり // 閾値を10^Aにする // 閾値以上の数は N=100/A // 組み合わせ全探索は 2^N // ナップサックは 10^A *100 *100 // 2^(100/x) = 10^(x+4) を解く、だいたい3.8 // 6400らしい // 本当かなぁ・・・ ll limit = 6400; ll mxval = 640000; vl more,less; REP(i,n){ if(a[i]>x)continue; if(a[i]>=limit)more.push_back(a[i]); else less.push_back(a[i]); } // 大きい値の全探索 vector X_S(mxval+10,false); if(x>mxval) REP(mask,1<>i&1)s+=more[i]; } if(x-s<0)continue; if(x-s>mxval)continue; X_S[x-s] = true; } // 小さい値のナップサック // vector dp(mxval+10,false); vector< vector > dp(n+1,vector(mxval+10,false)); vector< vector > pred(n+1,vector(mxval+10,false)); dp[0][0]=true; REP(i,less.size()){ ll cost = less[i]; REP(p,mxval+10){ if(!dp[i][p])continue; dp[i+1][p] = true; pred[i+1][p] = false; if(p+cost result; // ここに使う値をぶっこんでいく // dp,predから ll cst = ansid; REP(_i,less.size()){ ll i = less.size()-_i; if(pred[i][cst]){ result.insert(less[i-1]); cst -= less[i-1]; } } assert(cst==0); // 大きいやつ if(x>mxval) REP(mask,1<>i&1)s+=more[i]; } if(x-s==ansid){ REP(i,more.size()){ if(mask>>i&1)result.insert(more[i]); } break; } } multiset::iterator iter; REP(i,n){ iter = result.find(a[i]); if(iter!=result.end()){ cout<<"o"; result.erase(iter); }else{ cout<<"x"; } } cout<