oj.uz

Submission #91183

# Submission time Handle Problem Language Result Execution time Memory
91183 2018-12-26T13:16:11 Z emil_physmath Bootfall (IZhO17_bootfall) C++17
6 / 100
 1000 ms 123004 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];

void AllPossSums(int arr[], int n, vector<int> &);
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;
	AllPossSums(a, n, curSums);
	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]);
		AllPossSums(a, n-1, curSums);
		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;
}

void AllPossSums(int arr[], int n, vector<int> & res)
{
	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;
			}
		}
	}
	res.clear();
	for (int j=0; j<=sum; j++)
		if (dp[n][j]==true)
			res.push_back(j);
}

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 210 ms 122784 KB Output is correct
2 Correct 286 ms 122784 KB Output is correct
3 Correct 99 ms 122784 KB Output is correct
4 Correct 221 ms 122784 KB Output is correct
5 Correct 470 ms 122912 KB Output is correct
6 Correct 545 ms 122912 KB Output is correct
7 Correct 289 ms 122912 KB Output is correct
8 Correct 475 ms 122928 KB Output is correct
9 Correct 2 ms 122928 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 122784 KB Output is correct
2 Correct 286 ms 122784 KB Output is correct
3 Correct 99 ms 122784 KB Output is correct
4 Correct 221 ms 122784 KB Output is correct
5 Correct 470 ms 122912 KB Output is correct
6 Correct 545 ms 122912 KB Output is correct
7 Correct 289 ms 122912 KB Output is correct
8 Correct 475 ms 122928 KB Output is correct
9 Correct 2 ms 122928 KB Output is correct
10 Correct 866 ms 122932 KB Output is correct
11 Correct 897 ms 123004 KB Output is correct
12 Execution timed out 1024 ms 123004 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 122784 KB Output is correct
2 Correct 286 ms 122784 KB Output is correct
3 Correct 99 ms 122784 KB Output is correct
4 Correct 221 ms 122784 KB Output is correct
5 Correct 470 ms 122912 KB Output is correct
6 Correct 545 ms 122912 KB Output is correct
7 Correct 289 ms 122912 KB Output is correct
8 Correct 475 ms 122928 KB Output is correct
9 Correct 2 ms 122928 KB Output is correct
10 Correct 866 ms 122932 KB Output is correct
11 Correct 897 ms 123004 KB Output is correct
12 Execution timed out 1024 ms 123004 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 122784 KB Output is correct
2 Correct 286 ms 122784 KB Output is correct
3 Correct 99 ms 122784 KB Output is correct
4 Correct 221 ms 122784 KB Output is correct
5 Correct 470 ms 122912 KB Output is correct
6 Correct 545 ms 122912 KB Output is correct
7 Correct 289 ms 122912 KB Output is correct
8 Correct 475 ms 122928 KB Output is correct
9 Correct 2 ms 122928 KB Output is correct
10 Correct 866 ms 122932 KB Output is correct
11 Correct 897 ms 123004 KB Output is correct
12 Execution timed out 1024 ms 123004 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 122784 KB Output is correct
2 Correct 286 ms 122784 KB Output is correct
3 Correct 99 ms 122784 KB Output is correct
4 Correct 221 ms 122784 KB Output is correct
5 Correct 470 ms 122912 KB Output is correct
6 Correct 545 ms 122912 KB Output is correct
7 Correct 289 ms 122912 KB Output is correct
8 Correct 475 ms 122928 KB Output is correct
9 Correct 2 ms 122928 KB Output is correct
10 Correct 866 ms 122932 KB Output is correct
11 Correct 897 ms 123004 KB Output is correct
12 Execution timed out 1024 ms 123004 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 122784 KB Output is correct
2 Correct 286 ms 122784 KB Output is correct
3 Correct 99 ms 122784 KB Output is correct
4 Correct 221 ms 122784 KB Output is correct
5 Correct 470 ms 122912 KB Output is correct
6 Correct 545 ms 122912 KB Output is correct
7 Correct 289 ms 122912 KB Output is correct
8 Correct 475 ms 122928 KB Output is correct
9 Correct 2 ms 122928 KB Output is correct
10 Correct 866 ms 122932 KB Output is correct
11 Correct 897 ms 123004 KB Output is correct
12 Execution timed out 1024 ms 123004 KB Time limit exceeded
13 Halted 0 ms 0 KB -