Submission #51302

#	Time	Username	Problem	Language	Result	Execution time	Memory
51302		Nicksechko	Bootfall (IZhO17_bootfall)	C++14	0 / 100	27 ms	4076 KiB

bootfall

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <queue>
#include <unordered_map>
//#include <unordered_set>
#include <iomanip>
#include <stack>
#include <ctime>
#include <cassert>
#include <cmath>

#define y1 ups
#define left lll
#define right rrr
#define next nnn
//#define find fff

typedef unsigned long long ull;

using namespace std;

//mt19937_64 twister(chrono::steady_clock().now().time_since_epoch().count());
mt19937_64 twister(8888);

long long rnd(long long l, long long r)
{
    uniform_int_distribution<long long> dis(l, r);
    return dis(twister);
}

const int mod = (int)1e9 + 9;
//const int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
//const int st[2] = {887, 8887};'
const int maxn = 588;
const int inf = 1e4 + 88;
const int logn = 22;
const int maxa = 500*500 + 88;
const int block = 775;
const long long infll = 1e18 + 88;
const char sgl[5] = {'a', 'e', 'i', 'o', 'u'};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int knightx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int knighty[] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int kingx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int kingy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const char sep = 'a' - 1;
const double eps = 1e-9;
const int maxn1 = 1e3 + 88;

//#define int long long

int a[588];
int ans[maxa], dp[maxa];
int all_sum;
vector<int> v;

int msum(int a, int b)
{
    return (a + b)%mod;
}

void add(int x)
{
    all_sum += x;
    for (int i = maxa - x - 1; i >= 0; i--)
        dp[i + x] = msum(dp[i + x], dp[i]);
}

void del(int x)
{
    all_sum -= x;
    for (int i = 0; i + x < maxa; i++)
        dp[i + x] = msum(dp[i + x], mod - dp[i]);
}

void solve()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    int n, i, j;
    cin >> n;
    dp[0] = 1;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
        add(a[i]);
    }
    if ((all_sum&1) || dp[all_sum >> 1] == 0)
    {
        cout << 0;
        return;
    }
    for (i = 1; i < maxa; i++)
        ans[i] = true;
    for (i = 0; i < n; i++)
    {
        del(a[i]);
        for (j = 1; j < maxa; j++)
            if (((all_sum + j)&1) || dp[(all_sum + j) >> 1] == 0)
                ans[j] = false;
        add(a[i]);
    }
    for (i = 0; i < maxa; i++)
        if (ans[i])
            v.push_back(i);
    cout << v.size() << "\n";
    for (i = 0; i < v.size(); i++)
        cout << v[i] << " ";
}

//#undef int

int main()
{
//    srand(time(0));
//    srand(8);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
//    ifstream cin("output.txt");
//    ifstream fin("12.out");
//    int a, b, i = 0;
//    while (cin >> a)
//    {
//        fin >> b;
//        if (a != b)
//        {
//            cout << i << " " << a << " " << b;
//            return 0;
//        }
//        i++;
//    }
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    freopen("f.in", "r", stdin);
//    freopen("f.out", "w", stdout);
//    int t = 10000;
//    while (t--)
//    {
//        if (t == 9947)
//            t = 9947;
//        gen();
//        cout << t << endl;
//        brut();
//        if (!solve())
//        {
//            cout << "kek";
//            return 0;
//        }
//    }
    solve();
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'void solve()':
bootfall.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < v.size(); i++)
                 ~~^~~~~~~~~~
bootfall.cpp: In function 'int main()':
bootfall.cpp:147:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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