답안 #91183 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91183	2018-12-26T13:16:11 Z	emil_physmath	Bootfall (IZhO17_bootfall)	C++17	6 / 100	1000 ms	123004 KB

bootfall

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #91183

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0