結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 14 ms
4,376 KB
testcase_06 AC 14 ms
4,380 KB
testcase_07 AC 14 ms
4,376 KB
testcase_08 AC 15 ms
4,380 KB
testcase_09 AC 14 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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;

struct KV { int k, v; };

void swap(int& x, int& y) {
	int temp = x;
	x = y;
	y = temp;
	
	return;
}

void m_sort_(KV a[], KV 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].k <= a[rr].k); }
		
		if(flag) { b[bb++] = a[ll++]; }
		else     { b[bb++] = a[rr++]; }
	}
	
	FOR(i, l, r) { a[i] = b[i - l]; }
	
	return;
}
void m_sort(KV a[], int l, int r) {
	KV* b = new KV[r - l];
	m_sort_(a, b, l, r);
	delete[] b;
	
	return;
}


int n, s, p[31];
KV kv1[1 << 15];
KV kv2[1 << 16];
int ans[49], 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++] = kv1[aaa].v + (kv2[bbb].v << m);
			}
			}
			a = aa;
			b = bb;
		}
		if(sum < s) { a++; }
		if(sum > s) { b--; }
	}

	// 選択ソート
	DEC0(i, cnt) { int p = i;
	INC0(j,   i) {
		INC0(k, n) {
			if( (ans[j] ^ ans[p]) & (1 << k) ) {
				if(ans[p] & (1 << k)) { p = j; }
				break;
			}
		}
	} swap(ans[i], ans[p]);
	}
	
	INC0(i, cnt) {
		bool flag = false;
		INC0(j, n) {
			if(ans[i] & (1 << j)) {
				printf("%s%d", flag ? " " : "", j + 1);
				flag = true;
			}
		}
		printf("\n");
	}
	
	return 0;
}
0