Submission #393463

#	Time	Username	Problem	Language	Result	Execution time	Memory
393463		vanic	Bootfall (IZhO17_bootfall)	C++14	44 / 100	1091 ms	6628 KiB

bootfall

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <vector>

using namespace std;

const int maxn=505, Log=9, pot=(1<<Log);

int n;
int a[maxn];
bitset < maxn*maxn > dp[maxn];
bitset < maxn*maxn > sol;
vector < int > t[pot*2];
int tren;
int sum;
int sumuk;

void probaj(){
	dp[tren]=(dp[tren-1]>>((sum+2)/2));
	sol&=dp[tren];
}

void dodaj(int x){
	sum+=x;
	for(int i=sumuk; i>-1; --i){
		if(i>=x){
			dp[tren][i]=dp[tren-1][i-x]|dp[tren-1][i];
		}
		else{
			dp[tren][i]=dp[tren-1][i];
		}
	}
	tren++;
}

void update(int L, int D, int x, int l, int d, int val){
	if(L>=l && D<=d){
		t[x].push_back(val);
		return;
	}
	if((L+D)/2>=l){
		update(L, (L+D)/2, x*2, l, d, val);
	}
	if((L+D)/2+1<=d){
		update((L+D)/2+1, D, x*2+1, l, d, val);
	}
}


void query(int x){
//	cout << "na " << x << endl;
	for(int i=0; i<(int)t[x].size(); i++){
//		cout << "dodajem " << t[x][i] << endl;
		dodaj(t[x][i]);
	}
	if(x>=pot){
		if(x-pot<n){
			probaj();
		}
	}
	else{
		query(x*2);
		query(x*2+1);
	}
	for(int i=0; i<(int)t[x].size(); i++){
		sum-=t[x][i];
	}
	tren-=t[x].size();
}

void precompute(){
	for(int i=0; i<maxn*maxn; i++){
		sol[i]=1;
	}
}

int main(){
	scanf("%d", &n);
	int par=0, nep=0;
	precompute();
	for(int i=0; i<n; i++){
		scanf("%d", &a[i]);
		sumuk+=a[i];
		if(a[i]&1){
			nep++;
		}
		else{
			par++;
		}
	}
	if(par && nep){
		printf("0\n");
		return 0;
	}
	for(int i=0; i<n; i++){
		if(i){
			update(0, pot-1, 1, 0, i-1, a[i]);
		}
		if(i<n-1){
			update(0, pot-1, 1, i+1, pot-1, a[i]);
		}
	}
	dp[0][0]=1;
	for(int i=0; i<n; i++){
		for(int j=sumuk; j>=a[i]; j--){
			dp[0][j]=dp[0][j]|dp[0][j-a[i]];
		}
	}
	if((sumuk&1) || !dp[0][sumuk/2]){
		printf("0\n");
		return 0;
	}
	dp[0].reset();
	dp[0][0]=1;
	tren=1;
	query(1);
	printf("%d\n", (int)sol.count());
	for(int i=0; i<maxn*maxn; i++){
		if(sol[i]){
			if(par){
				printf("%d " , (i+1)*2);
			}
			else{
				printf("%d " , (i+1)*2-1);
			}
		}
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bootfall.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~

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