Submission #475352

#	Time	Username	Problem	Language	Result	Execution time	Memory
475352		ismoilov	Bootfall (IZhO17_bootfall)	C++14	100 / 100	279 ms	49124 KiB

bootfall

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int maxx = 505;

vector <int> ach[maxx*4];
bitset<maxx*maxx> pos[maxx*4];

//node tr[maxx*4];

bitset <maxx*maxx> out[maxx];
void update(int l, int r, int tl, int tr, int id, int val){
//	cout << tl << " " << tr << " " << val << " done\n";
	if(l > tr || r < tl)
		return;
	if(l >= tl && r <= tr){
		ach[id].push_back(val);
	//	cout << "added " << l << " " << r  << " " << id << "\n";
		return;
	}
	int m = (l + r) / 2;
	update(l, m, tl, tr, id+id, val);
	update(m+1, r, tl ,tr, id+id+1, val);
//	cout << "finally\n";
}

void build(int l, int r, int id){
	pos[id][0] = 1;
	for(auto it : ach[id])
		pos[id] |= (pos[id] << it);
	
	if(l == r){
		out[l] = pos[id];
		return;
	}
	
	int m = (l + r) / 2;
	pos[id+id] = pos[id];
	pos[id+id+1] = pos[id];
	build(l, m, id+id);
	build(m+1, r, id+id+1);
}

void S()
{
	int n;
	cin >> n;
	vector <int> a(n+1);
	int s = 0;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		s += a[i];
	}
	if(s % 2 == 1){
		cout << 0;
		return;
	}
	
	for(int i = 1; i <= n; i ++){
		update(1, n+1, 1, i-1, 1, a[i]);
		update(1, n+1, i+1, n+1, 1, a[i]);
	}
//	cout << s;/*
	build(1, n+1, 1);
	
	if(out[n+1][s/2] == 0){
		cout << 0;
		return;
	}
	
	vector <int> ans;
	for(int can = 1; can <= s; can ++){
		bool ok = 1;
		for(int i = 1; i <= n; i ++){
			int s1 = s - a[i] + can;
			if(s1 % 2 == 1 || out[i][s1/2] == 0){
				ok = 0;
				break;
			}
		}
		if(ok)
			ans.push_back(can);
	}
	cout << ans.size() << "\n";
	for(auto it : ans)
		cout << it << " ";
}

int main()
{
	IOS;
	/*int t;
	cin >> t;
	while(t --)*/
		S();
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35