#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らしい // 本当かなぁ・・・ // なんか無駄に枝刈りしちゃってるけど全部組み合わせて良くない? // ナップサックは元々並んでるけど、大きい値の方は全部の組み合わせをsetにでも突っ込んで ll limit = 10000; ll mxval = limit*100; 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); map XS; REP(mask,1<>i&1)s+=more[i]; } if(s>x)continue; XS[s] = mask; // if(0<=x-s && x-s<=mxval){ // X_S[x-s]=true; // }else if(0 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); ll mask = XS[x-ansid]; REP(i,more.size()){ if(mask>>i&1)result.insert(more[i]); } // // s==x-ansid // // s==cst // if(x-ansid == cst){ // cout << "No" << endl; // return 0; // } // // 大きいやつ // vl ansmsk, cstmsk; // REPR(mask,1<>i&1)s+=more[i]; // } // if(x-s==ansid || s==cst){ // if(x-s==ansid){ // ansmsk.push_back(mask); // } // if(s==cst){ // cstmsk.push_back(mask); // } // 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<