oj.uz

Submission #91178

# Submission time Handle Problem Language Result Execution time Memory
91178 2018-12-26T13:04:04 Z emil_physmath Bootfall (IZhO17_bootfall) C++14
6 / 100
 1000 ms 123240 KB 
#include <iostream>
#include <stdio.h>
#include <unordered_set>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
const int MAXN=500, MAXSUM=500*500;

int a[MAXN+1];
bool dp[MAXN][MAXSUM+1];

vector<int> AllPossSums(int arr[], int n);
int main()
{
	int n, sum=0;
	cin>>n;
	set<int> mods;
	for (int i=0; i<n; i++)
	{
		scanf("%d", a+i);
		mods.insert(a[i]%2);
		sum+=a[i];
	}
	if (mods.size()>1)
	{
		cout<<"0\n";
		return 0;
	}
	if (*(mods.begin()))
		if (n%2)
		{
			cout<<"0\n";
			return 0;
		}
	vector<int> curSums;
	curSums=AllPossSums(a, n);
	bool f=false;
	for (int i=0; i<curSums.size(); i++)
		if (curSums[i]*2==sum)
		{
			f=true;
			break;
		}
	if (!f)
	{
		cout<<"0\n";
		return 0;
	}
	unordered_set<int> ans;
	for (int i=0; i<n; i++)
	{ // #i doesn't play.
		sum-=a[i];
		swap(a[i], a[n-1]);
		curSums=AllPossSums(a, n-1);
		unordered_set<int> curAns;
		for (int j=0; j<curSums.size(); j++)
			curAns.insert(abs((sum-curSums[j])-curSums[j]));
		if (!i)
		{
			ans=curAns;
			swap(a[i], a[n-1]);
			sum+=a[i];
			continue;
		}
		unordered_set<int> temp;
		for (auto it=curAns.begin(); it!=curAns.end(); it++)
			if (ans.find(*it)!=ans.end())
			{
				temp.insert(*it);
				ans.erase(*it);
				//curAns.erase(*it);
			}
		ans=temp;
		swap(a[i], a[n-1]);
		sum+=a[i];
	}
	cout<<ans.size()<<'\n';
	set<int> ansOut(ans.begin(), ans.end());
	for (auto it=ansOut.begin(); it!=ansOut.end(); it++)
		cout<<*it<<' ';
	cout<<endl;

	char I;
	cin >> I;
	return 0;
}

vector<int> AllPossSums(int arr[], int n)
{
	int sum=0;
	for (int i=0; i<n; i++)
		sum+=arr[i];
	memset(dp, 0, sizeof(dp));
	for (int i=0; i<=n; i++)
		dp[i][0]=true;
	for (int i=1; i<=n; i++)
	{
		dp[i][arr[i-1]]=true;
		for (int j=1; j<=sum; j++)
		{
			if (dp[i-1][j]==true)
			{
				dp[i][j]=true;
				dp[i][j+arr[i-1]]=true;
			}
		}
	}
	vector<int> res;
	for (int j=0; j<=sum; j++)
		if (dp[n][j]==true)
			res.push_back(j);
	return res;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<curSums.size(); i++)
                ~^~~~~~~~~~~~~~~
bootfall.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<curSums.size(); j++)
                 ~^~~~~~~~~~~~~~~
bootfall.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
   ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 122672 KB Output is correct
2 Correct 273 ms 122876 KB Output is correct
3 Correct 97 ms 122876 KB Output is correct
4 Correct 180 ms 122876 KB Output is correct
5 Correct 384 ms 122880 KB Output is correct
6 Correct 272 ms 122880 KB Output is correct
7 Correct 287 ms 122880 KB Output is correct
8 Correct 392 ms 122940 KB Output is correct
9 Correct 2 ms 122940 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 122672 KB Output is correct
2 Correct 273 ms 122876 KB Output is correct
3 Correct 97 ms 122876 KB Output is correct
4 Correct 180 ms 122876 KB Output is correct
5 Correct 384 ms 122880 KB Output is correct
6 Correct 272 ms 122880 KB Output is correct
7 Correct 287 ms 122880 KB Output is correct
8 Correct 392 ms 122940 KB Output is correct
9 Correct 2 ms 122940 KB Output is correct
10 Correct 750 ms 123208 KB Output is correct
11 Correct 949 ms 123208 KB Output is correct
12 Correct 810 ms 123208 KB Output is correct
13 Correct 2 ms 123208 KB Output is correct
14 Correct 717 ms 123208 KB Output is correct
15 Correct 709 ms 123208 KB Output is correct
16 Correct 896 ms 123208 KB Output is correct
17 Correct 635 ms 123208 KB Output is correct
18 Correct 838 ms 123208 KB Output is correct
19 Correct 909 ms 123240 KB Output is correct
20 Execution timed out 1037 ms 123240 KB Time limit exceeded

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 122672 KB Output is correct
2 Correct 273 ms 122876 KB Output is correct
3 Correct 97 ms 122876 KB Output is correct
4 Correct 180 ms 122876 KB Output is correct
5 Correct 384 ms 122880 KB Output is correct
6 Correct 272 ms 122880 KB Output is correct
7 Correct 287 ms 122880 KB Output is correct
8 Correct 392 ms 122940 KB Output is correct
9 Correct 2 ms 122940 KB Output is correct
10 Correct 750 ms 123208 KB Output is correct
11 Correct 949 ms 123208 KB Output is correct
12 Correct 810 ms 123208 KB Output is correct
13 Correct 2 ms 123208 KB Output is correct
14 Correct 717 ms 123208 KB Output is correct
15 Correct 709 ms 123208 KB Output is correct
16 Correct 896 ms 123208 KB Output is correct
17 Correct 635 ms 123208 KB Output is correct
18 Correct 838 ms 123208 KB Output is correct
19 Correct 909 ms 123240 KB Output is correct
20 Execution timed out 1037 ms 123240 KB Time limit exceeded

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 122672 KB Output is correct
2 Correct 273 ms 122876 KB Output is correct
3 Correct 97 ms 122876 KB Output is correct
4 Correct 180 ms 122876 KB Output is correct
5 Correct 384 ms 122880 KB Output is correct
6 Correct 272 ms 122880 KB Output is correct
7 Correct 287 ms 122880 KB Output is correct
8 Correct 392 ms 122940 KB Output is correct
9 Correct 2 ms 122940 KB Output is correct
10 Correct 750 ms 123208 KB Output is correct
11 Correct 949 ms 123208 KB Output is correct
12 Correct 810 ms 123208 KB Output is correct
13 Correct 2 ms 123208 KB Output is correct
14 Correct 717 ms 123208 KB Output is correct
15 Correct 709 ms 123208 KB Output is correct
16 Correct 896 ms 123208 KB Output is correct
17 Correct 635 ms 123208 KB Output is correct
18 Correct 838 ms 123208 KB Output is correct
19 Correct 909 ms 123240 KB Output is correct
20 Execution timed out 1037 ms 123240 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 122672 KB Output is correct
2 Correct 273 ms 122876 KB Output is correct
3 Correct 97 ms 122876 KB Output is correct
4 Correct 180 ms 122876 KB Output is correct
5 Correct 384 ms 122880 KB Output is correct
6 Correct 272 ms 122880 KB Output is correct
7 Correct 287 ms 122880 KB Output is correct
8 Correct 392 ms 122940 KB Output is correct
9 Correct 2 ms 122940 KB Output is correct
10 Correct 750 ms 123208 KB Output is correct
11 Correct 949 ms 123208 KB Output is correct
12 Correct 810 ms 123208 KB Output is correct
13 Correct 2 ms 123208 KB Output is correct
14 Correct 717 ms 123208 KB Output is correct
15 Correct 709 ms 123208 KB Output is correct
16 Correct 896 ms 123208 KB Output is correct
17 Correct 635 ms 123208 KB Output is correct
18 Correct 838 ms 123208 KB Output is correct
19 Correct 909 ms 123240 KB Output is correct
20 Execution timed out 1037 ms 123240 KB Time limit exceeded

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 122672 KB Output is correct
2 Correct 273 ms 122876 KB Output is correct
3 Correct 97 ms 122876 KB Output is correct
4 Correct 180 ms 122876 KB Output is correct
5 Correct 384 ms 122880 KB Output is correct
6 Correct 272 ms 122880 KB Output is correct
7 Correct 287 ms 122880 KB Output is correct
8 Correct 392 ms 122940 KB Output is correct
9 Correct 2 ms 122940 KB Output is correct
10 Correct 750 ms 123208 KB Output is correct
11 Correct 949 ms 123208 KB Output is correct
12 Correct 810 ms 123208 KB Output is correct
13 Correct 2 ms 123208 KB Output is correct
14 Correct 717 ms 123208 KB Output is correct
15 Correct 709 ms 123208 KB Output is correct
16 Correct 896 ms 123208 KB Output is correct
17 Correct 635 ms 123208 KB Output is correct
18 Correct 838 ms 123208 KB Output is correct
19 Correct 909 ms 123240 KB Output is correct
20 Execution timed out 1037 ms 123240 KB Time limit exceeded