Submission #36249

#	Time	Username	Problem	Language	Result	Execution time	Memory
36249		touristk2000	Bootfall (IZhO17_bootfall)	C++14	100 / 100	253 ms	4556 KiB

bootfall

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;
 
#define mk make_pair
#define inb push_back
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define sqr(x) (x) * (x)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define y1 AYDARBOG

const int BUFSZ = (int)1e5 + 7;
char buf[BUFSZ];
string get_str()
{
    scanf(" %s", buf);
    return string(buf);
}
 
struct Item
{
    int l, r, val;
    Item() {};
    Item(int l, int r, int val) : l(l), r(r), val(val) {};
    void print()
    {
        printf("%d %d %d\n", l, r, val);
    }
};
 
bool intersect(int l, int r, int l1, int r1)
{
    if (l > l1)
        swap(l, l1), swap(r, r1);
    return l1 <= r;
}
 
void dfs(int tl, int tr, int sum, vector<Item> &q, bitset<250001> &dp, vector<int> &cnt)
{
    vector<Item> ql, qr;
    for (auto &x : q)
    {
        if (x.l <= tl && tr <= x.r)
        {
            sum += x.val;
            dp |= dp << x.val;
        }
    }
    if (tl == tr)
    {
        for (int i = 0; i < 250001 && 2 * i < sum; ++i)
        {
            if (!dp[i])
                continue;
            ++cnt[sum - 2 * i];
        }
        return;
    }
    int tm = tl + tr >> 1;
    for (auto &x : q)
    {
        if (x.l <= tl && tr <= x.r)
            continue;
        if (intersect(x.l, x.r, tl, tm))
            ql.inb(x);
        if (intersect(x.l, x.r, tm + 1, tr))
            qr.inb(x);
    }
    q.clear();
    bitset<250001> ndp = dp;
    dfs(tl, tm, sum, ql, dp, cnt);
    dfs(tm + 1, tr, sum, qr, ndp, cnt);
}
 
int solve()
{
    int n;
    scanf("%d", &n);
    vi a(n);
    int sum = 0;
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]), sum += a[i];
    vector<int> cnt(250001);
    bitset<250001> dp;
    {
        dp = dp.reset();
        dp[0] = 1;
        for (int i = 0; i < n; ++i)
        {
            dp |= dp << a[i];
        }
        if (!dp[sum / 2])
            puts("0"), exit(0);
    }
    vector<Item> q;
    for (int i = 0; i < n; ++i)
    {
        if (i)
            q.inb(Item(0, i - 1, a[i]));
        if (i < n - 1)
            q.inb(Item(i + 1, n - 1, a[i]));
    }
    dp.reset();
    dp[0] = 1;
    dfs(0, n - 1, 0, q, dp, cnt);
    vi ans;
    for (int i = 0; i < 250001; ++i)
    {
        if (cnt[i] == n)
            ans.inb(i);
    }
    printf("%d\n", (int)ans.size());
    for (int x : ans)
        printf("%d ", x);
    puts("");
    return 0;
}

int main(){
    
    solve();
}

Compilation message (stderr)

bootfall.cpp: In function 'void dfs(int, int, int, std::vector<Item>&, std::bitset<250001ul>&, std::vector<int>&)':
bootfall.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
                 ^
bootfall.cpp: In function 'std::__cxx11::string get_str()':
bootfall.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", buf);
                      ^
bootfall.cpp: In function 'int solve()':
bootfall.cpp:85:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
bootfall.cpp:89:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]), sum += a[i];
                                        ^

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