結果

問題 No.15 カタログショッピング
コンテスト
ユーザー ynq1242
提出日時 2014-10-29 12:37:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 51 ms / 5,000 ms
コード長 2,244 bytes
コンパイル時間 1,193 ms
コンパイル使用メモリ 94,800 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2024-12-30 13:38:10
合計ジャッジ時間 2,060 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<list>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
#include<ctime>
#include<set>
using namespace std;


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define F first
#define S second
#define endl "\n"
#define pp(X)		cout<<X.F<<"\t"<<X.S<<endl
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

li p[32];

void reverse_bit(li &x, li n){
	li res=0;
	rep(i,n){
		if((bit(i)&x)>0)res+=bit(n-i-1);
	}
	x=res;
}

int main(){
	ios::sync_with_stdio(false);
	li n, s;
	cin>>n>>s;

	rin{cin>>p[i];}
	if(n==1){
		if(p[0]==s)puts("1");
		return 0;
	}

	li mid=n/2;

	multimap<li, li> sum1, sum2;

	rep(i,bit(mid)){
		li sum=0;
		rep(j,mid){
			if(((1ll<<j)&i)>0)sum+=p[j];
		}
		sum1.insert(mp(sum,i));
	}

	rep(i,bit(n-mid)){
		li sum=0;
		rep(j,n-mid){
			if(((1ll<<j)&i)>0)sum+=p[j+mid];
		}
		sum2.insert(mp(s-sum,i));
	}

	//for(map<li,li>::iterator it=sum1.begin(); it!=sum1.end(); ++it)pp((*it));
	//for(map<li,li>::iterator it=sum2.begin(); it!=sum2.end(); ++it){cout<<"--- "; pp((*it));}

	vector<li> res;
	for(multimap<li,li>::iterator it=sum1.begin(); it!=sum1.end(); ++it){
		multimap<li,li>::iterator it2=sum2.lower_bound(it->F);
		while(it2!=sum2.end() && it2->F==it->F){
			//p2(it->F, it2->F);
			res.pb((it2->S<<mid)+it->S);
			++it2;
		}
	}
	rep(i,sz(res))reverse_bit(res[i], n);
	sort(allof(res));
	reverse(allof(res));

	rep(i,sz(res)){
		rep(j,n)if((bit(n-1-j)&res[i])>0)cout<<j+1<<" ";
		cout<<endl;
	}

	return 0;
}
0