No.15 カタログショッピング - yukicoder
- 蟻本ででてたやつ。前半・後半全列挙 + 二分探索
- 方針もあっていたし、コードも間違っていないっぽくて手元のローカルではサンプル通ったのにサーバ側でWAになってしまった。
- 最後の出力時に無駄に空白が入っていたのが原因。本当につまんないミスするなぁ...。
class CatalogueShopping {
public:
void solve(void) {
int N;
ll S;
cin>>N>>S;
vector<ll> P(N);
REP(i, N)
cin>>P[i];
vector<pair<ll,int>> S1;
int m = N;
if (m > 16)
m = 16;
for (int b = 0; b < (1<<m); ++b)
{
ll sum = 0;
FOR(i,1,m+1) if (b & (1<<(m-i)))
sum += P[i-1];
S1.emplace_back(sum, b);
}
sort(RANGE(S1));
vector<ll> S2((1<<(N-m)), 0);
for (int b = 0; b < (1<<(N-m)); ++b)
{
FOR(i,1,N-m+1) if (b & (1<<(N-m-i)))
S2[b] += P[i+m-1];
}
vector<int> combs;
REP(b2, 1<<(N-m))
{
ll s2 = S2[b2];
if (s2 == S)
{
combs.push_back(b2);
continue;
}
auto it1 = lower_bound(RANGE(S1), make_pair(S-s2, -1));
auto it2 = upper_bound(RANGE(S1), make_pair(S-s2, (1<<30)));
if (it1 == S1.end() || it1->first != S-s2)
continue;
while (it1 != it2)
{
int b1;
ll s1;
tie(s1,b1) = *it1;
combs.push_back(b1<<(N-m) | b2);
++it1;
}
}
sort(RANGE(combs), greater<int>());
for (auto b : combs)
{
string ans;
FOR(i,1,N+1) if (b & (1<<(N-i)))
ans+=to_string(i)+" ";
cout<<ans.substr(0,ans.length()-1)<<endl;
}
}
};