Submission #910264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
910264	2024-01-18T03:23:52 Z	vjudge1	Bootfall (IZhO17_bootfall)	C++17	6 / 100	1000 ms	860 KB

bootfall

/*
   (( '-""``""-' ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / ;#'#'# - #'#'#; \
 \_)) -----'#'----- ((_/
      # --------- #
      '# ------- #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))
    art by - Vinni01 / luchi abi
 
    cout << fixed << setprecision(6) << x;
    freopen ( "sum.in", "r", stdin )
*/
#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>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
using namespace std ;
#define ll int
#define dd double
#define ff first
#define ss second
#define pb push_back 
#define pf push_front
#define UseOFF ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);
#define sz size
#define ins insert
#define new jweijofdg
const ll N = 500 + 11 ;
ll tt = 1 ;
ll a[ N ] ;
set < ll > st[ N * 12 ] ;
void solve()
{
	ll n ;
	cin >> n ;
	ll pos = 0 ;
	ll sum = 0 ;
	ll mn = 1e9 ;
	for( int i = 0 ; i < n ; i++ )
	{
		cin >> a[ i ] ;
		sum += a[ i ] ;
		mn = min( mn, a[ i ] ) ;
	}
	bool b = 0 ;
	sum -= mn ;
	ll cnt = 0 ;
	for( int l = -1 ; l < n ; l++ )
	{
		ll prev ;
		if( l >= 0 ) prev = a[ l ] ;
		if( l >= 0 ) a[ l ] = 0 ;
		for( int i = 1 ; i < ( 1 << n ) ; i++ )
		{
			ll sum1 = 0, sum2 = 0 ;
			for( int j = 0 ; j < n ; j++ )
			{
				if( ( i >> j ) & 1 )
				{
					sum1 += a[ j ] ;
				}
				else sum2 += a[ j ] ;
			}
			ll d = abs( sum1 - sum2 ) ;
			st[ d ].ins( l ) ;
			if( l == -1 )
			{
				if( d == 0 )
				{
					b = 1 ;
				}
			}
		}
		if( l >= 0 ) a[ l ] = prev ;
	}
	if( b == 0 )
	{
		cout << "0" ;
		return ;
	}
	vector < ll > v ;
	for( int i = 1 ; i <= sum ; i++ )
	{
		if( st[ i ].sz() == n )
		{
			v.pb( i ) ;
		}
	}
	cout << v.sz() << '\n' ;
	for( auto to : v )
	{
		cout << to << " " ;
	}
}
signed main()
{
	while( tt-- )
	{
		solve() ;
	}
}

Compilation message

bootfall.cpp: In function 'void solve()':
bootfall.cpp:112:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |   if( st[ i ].sz() == n )
      |       ~~~~~~~~~~~~~^~~~
bootfall.cpp:64:5: warning: unused variable 'pos' [-Wunused-variable]
   64 |  ll pos = 0 ;
      |     ^~~
bootfall.cpp:75:5: warning: unused variable 'cnt' [-Wunused-variable]
   75 |  ll cnt = 0 ;
      |     ^~~

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	4 ms	860 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	4 ms	860 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Execution timed out	1047 ms	600 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	4 ms	860 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Execution timed out	1047 ms	600 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	4 ms	860 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Execution timed out	1047 ms	600 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	4 ms	860 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Execution timed out	1047 ms	600 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #6

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	4 ms	860 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	4 ms	860 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Execution timed out	1047 ms	600 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-