#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]; // 考察は正しかった // 閾値limitを設けて分ける // O(N) // 閾値より大きい奴は組み合わせを全探索してmapにmaskと合わせて突っ込む // O(2^A log 2^A) = O(A 2^A) // 閾値より小さい奴は0-1ナップサックをする 復元ができるように // O(B limit*N) // 合成する // O(limit*N log 2^A) = O(limit*N A) // 復元する ここではmultisetに使用する値を入れていく // 全探索: O(A logN) // ナップサック: O(B limit*N logN) // 出力する 元の数列を見て、multisetにあるかどうかを確認する // O(NlogN) // Bは最悪NなのでNを想定すると // O(A2^A + N^2 limit logN) なお AlogN <= N^2 // Aの最悪はlimitによって、limit^A<=10^100である // A log_10(limit) <= 100 より、A<=100/log_10(limit) // limit = 10^Lとすると、log_10(limit)=Lで、A<=100/L // よって O(100/L 2^(100/L) + N^2 logN 10^L) // これを最小化するLは4.03ぐらい // よって閾値を10^4.03 = 10715にする ll limit = 10715; ll mxval = limit*n; 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]); } // 大きい値の全探索 map XS; REP(mask,1<>i&1)s+=more[i]; } if(s>x)continue; XS[s] = mask; } // 小さい値のナップサック 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); // 全探索のmaskから ll mask = XS[x-ansid]; REP(i,more.size()){ if(mask>>i&1)result.insert(more[i]); } // 出力 multiset::iterator iter; REP(i,n){ iter = result.find(a[i]); if(iter!=result.end()){ cout<<"o"; result.erase(iter); }else{ cout<<"x"; } } cout<