結果

問題 No.15 カタログショッピング
ユーザー FF256grhyFF256grhy
提出日時 2016-09-03 18:46:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 16 ms / 5,000 ms
コード長 2,420 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 30,104 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-09 21:23:26
合計ジャッジ時間 1,052 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,384 KB
testcase_05 AC 15 ms
4,376 KB
testcase_06 AC 16 ms
4,380 KB
testcase_07 AC 15 ms
4,380 KB
testcase_08 AC 15 ms
4,376 KB
testcase_09 AC 15 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘bool Bit::operator<=(const Bit&)’:
main.cpp:58:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

ソースコード

diff # 

#include <cstdio>

#define FOR(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define REV(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define INC0(i, n) FOR(i, 0, n)
#define INC1(i, n) FOR(i, 1, (n) + 1)
#define DEC0(i, n) REV(i, 0, n)
#define DEC1(i, n) REV(i, 1, (n) + 1)

typedef long long   signed int LL;
typedef long long unsigned int LU;

template<typename T> void m_sort_(T a[], T b[], int l, int r) {
	if(r - l < 2) { return; }
	
	int m = (l + r) / 2;
	m_sort_(a, b, l, m);
	m_sort_(a, b, m, r);
	
	int ll = l, rr = m, bb = 0;
	while(bb < r - l) {
		bool flag;
		if(rr == r || ll == m) { flag = (rr == r); }
		else { flag = (a[ll] <= a[rr]); }
		
		if(flag) { b[bb++] = a[ll++]; }
		else     { b[bb++] = a[rr++]; }
	}
	
	FOR(i, l, r) { a[i] = b[i - l]; }
	
	return;
}
template<typename T> void m_sort(T a[], int l, int r) {
	T* b = new T[r - l];
	m_sort_(a, b, l, r);
	delete[] b;
	
	return;
}


struct KV {
	int k, v;
	bool operator<=(const KV& obj) { return this -> k <= obj.k; }
};

struct Bit {
	int v;
	bool operator<=(const Bit& obj) {
		if(this -> v == obj.v) { return true; }
		
		INC0(i, 31) {
			if( ((this -> v) ^ obj.v) & (1 << i) ) {
				return ((this -> v) & (1 << i));
			}
		}
	}
	void print(int n) {
		bool flag = false;
		INC0(j, n) {
			if(v & (1 << j)) {
				printf("%s%d", flag ? " " : "", j + 1);
				flag = true;
			}
		}
		printf("\n");
	}
};


int n, s, p[31];
KV kv1[1 << 15];
KV kv2[1 << 16];
Bit ans[49]; int cnt;

int main() {
	scanf("%d%d", &n, &s);
	INC0(i, n) { scanf("%d", &p[i]); }
	
	int m = n / 2;
	
	INC0(i, 1 << m) {
		int sum = 0;
		FOR(j, 0, m) {
			if(i & (1 << j)) { sum += p[j]; }
		}
		kv1[i].k = sum;
		kv1[i].v = i;
	}
	
	INC0(i, 1 << (n - m)) {
		int sum = 0;
		FOR(j, 0, n - m) {
			if(i & (1 << j)) { sum += p[m + j]; }
		}
		kv2[i].k = sum;
		kv2[i].v = i;
	}
	
	m_sort(kv1, 0, 1 << m);
	m_sort(kv2, 0, 1 << (n - m));
	
	int a = 0, b = (1 << (n - m)) - 1;
	while(a < (1 << m) && b >= 0) {
		int ka = kv1[a].k;
		int kb = kv2[b].k;
		int sum = ka + kb;
		if(sum == s) {
			int aa = a, bb = b;
			while(aa <  (1 << m) && kv1[aa].k == ka) { aa++; }
			while(bb >=       0  && kv2[bb].k == kb) { bb--; }
			FOR(aaa, a, aa) {
			FOR(bbb, bb + 1, b + 1) {
				ans[cnt++].v = kv1[aaa].v + (kv2[bbb].v << m);
			}
			}
			a = aa;
			b = bb;
		}
		if(sum < s) { a++; }
		if(sum > s) { b--; }
	}
	
	m_sort(ans, 0, cnt);
	
	INC0(i, cnt) { ans[i].print(n); }
	
	return 0;
}
0