Submission #39323

#	Time	Username	Problem	Language	Result	Execution time	Memory
39323		Scayre	Bootfall (IZhO17_bootfall)	C++14	6 / 100	1000 ms	29928 KiB

bootfall

//
// omae wa mou shindeiru.
//
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
 
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
 
#define ll long long
#define ull unsigned ll
#define ioi exit(0);
 
#define f first
#define s second
 
#define inf (int)1e9 + 7
 
#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
#define mp make_pair
 
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
 
#define pb push_back
#define ppb pop_back
 
#define endl "\n"
 
#define in(x) insert(x)
 
#define sz(x) (int)x.size()
 
#define all(x) x.begin(),x.end()
 
#define pw2(x) (1<<x) //2^x
 
#define sqr(x) ((x) * 1ll * (x))
 
using namespace std;
 
const int N = (int)5e5 + 7, MOD = (int)1e9 + 7;
 
vector <int> v;

int n;

int a[N];

bool pass=0;
 
map <int,bool> m[N];

void rec(int x,int l,int r,int v){
	if(x==v){
		rec(x+1,l,r,v);
		return;
	}
	if(x>n){
		m[v][abs(l-r)]=1;
		return;
	}
	rec(x+1,l+a[x],r,v);
	rec(x+1,l,r+a[x],v);
}

void ch(int x,int l,int r){
	if(x>n){
		if(l==r){
			pass=1;
		}
		return;
	}
	ch(x+1,l+a[x],r);
	ch(x+1,l,r+a[x]);
}

int main(){ 
 
	#ifdef IOI2019
		freopen ("in.txt", "r", stdin);
	#endif
 
	//NFS
 
	cin >> n;

	for(int i=1;i<=n;i++){
		cin >> a[i];
	}

	ch(1,0,0);

	if(pass==0){
		cout << 0 << endl;
		ioi
	}

	for(int i=1;i<=n;i++){
		rec(1,0,0,i);
	}

	for(int i=1;i<=50000;i++){
		bool ok=1;
		for(int j=1;j<=n;j++){
			if(m[j][i]==0){
				ok=0;
				break;
			}
		}
		if(ok==1){
			v.pb(i);
		}
	}

	cout << sz(v) << endl;

	for(int i=0;i<v.size();i++){
		cout << v[i] << ' ';
	}

	#ifdef IOI2019
		cout << "\nTime Elapsed : " << clock () * 1.0 / CLOCKS_PER_SEC << endl;
	#endif
 
	ioi
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:141:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
               ^

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