Codeforces 356(#207 Div1) D. Bags and Coins

問題

n枚の袋があって、i番目の袋の中にはa[i]枚のコインが入っている。コインは全体でs枚である。

ただし、袋の中にはさらに別の袋が入っていることがある。
a[i] = {1, 1, 3}で、全体でコインが3枚ということがある。
（3番目の袋には1番目の袋と2番目の袋とコインが一枚入っている状態が考えられる）

袋とコインの状態としてありうるものをどれか一通り出力せよ。
存在しない場合は-1を出力せよ。

制約条件

n, s, a[i]≦70000

方針

袋を全く入れ子にしないとするとコインの枚数はΣa[i]枚。
i番目の袋をj番目の袋に入れるとコインの総数はa[i]枚だけ減る。

つまり、減らさない袋を上手く選んでΣ{a[i] | i∈減らさない袋} = sにすればよい。
一番コインの入っている袋さえ使えば、どのような集合の選び方でも上手くいく。
（コインの少ない順に袋を並べたときに、次の袋に入れるようにすればよいから）

なので、ナップサック（partition問題）＋経路復元を解けばよい。
だけなんだけど、品物と容量が大きいので解けない。
ビット並列化が必要。
でもメモリが足りないので、分割統治的に前半でx, 後半でs - xを作れるか見て、
作れるなら前半を更に再帰、後半も再帰……と経路復元ができる大きさまで分割してやる。

正直クソ問すぎる（解法は思いついてたけど、これが想定解のわけないだろうなと思ってた）けど、bitsetの使い方がわかったのでまあよい。

ソースコード

const int N = 20000;
int n, s, a[70000];
bool use[70000];

typedef bitset<70001> B;
B dp[N];

inline const B check(int l, int r){
	B res;
	res[0] = 1;
	for(int i = l; i < r; i++) res |= res << a[i];
	return res;
}
inline bool can(int l, int r, int s){
	
	if(r - l < N){
		dp[0] = 1;
		for(int i = l, j = 0; i < r; i++, j++) dp[j + 1] = dp[j] | dp[j] << a[i];
		if(!dp[r - l][s]) return 0;
		for(int i = r - 1, j = r - l - 1; i >= l; i--, j--){
			if(s >= a[i] && dp[j][s - a[i]]){
				s -= a[i];
				use[i] = 1;
			}
		}
		return 1;
	}
	
	int m = (l + r) / 2;
	const B dp1 = check(l, m), dp2 = check(m, r);
	
	rep(i, s + 1) if(dp1[i] && dp2[s - i]){
		
		return can(l, m, i) && can(m, r, s - i);
	}
	return 0;
}

int main(){
	scanf("%d%d", &n, &s);
	
	vector<pi> v;
	rep(i, n){
		scanf("%d", a + i);
		v.pb(mp(a[i], i));
	}
	static int to[70000];
	sort(all(v));
	sort(a, a + n);
	rep(i, n) to[v[i].second] = i;
	
	if(a[n - 1] > s){
		cout << -1 << endl;
		return 0;
	}
	use[n - 1] = 1;
	s -= a[n - 1];
	int m = n - 1;
	for(; m > 0 && a[m - 1] > s; m--);
	
	if(!can(0, m, s)){
		cout << -1 << endl;
		return 0;
	}
	
	rep(ii, n){
		int i = to[ii];
		if(i && !use[i - 1]) printf("%d 1 %d\n", a[i] - a[i - 1], v[i - 1].second + 1);
		else printf("%d 0\n", a[i]);
	}
	
	return 0;
}