Submission #1367707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367707		jbn8	Bootfall (IZhO17_bootfall)	C++20	28 / 100	1097 ms	17628 KiB

bootfall

#include <cstdio>
#include <array>
#include <cassert>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 500;
const int maxA = 501;
int main(){
    int N;
    scanf("%d\n", &N);
    array<int, maxN+1> a{};
    int sum = 0;
    for(int i=0; i<N; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    array<int, maxA*maxN> poss{};
    array<bool, maxN*maxA/2> cache{};
    array<vector<int>, maxN*maxA/2> path{};
    array<int, maxN> already{};
    cache[0] = true;
    sort(a.begin(), a.begin()+N);
    int duplicate = 0;
    for(int i=0; i<N; i++){
        already[a[i]] = i;
        int idp = i;
        for(int j=sum/2; j >= 0; j--){
            if(cache[j]){
                cache[j+a[idp]] = true;
                path[j+a[idp]].push_back(idp);
            }
        }
    }
    if(!cache[sum/2] || sum%2 != 0){
        printf("0\n");
        return 0;
    }
    array<bool, maxN> isInStack;

    function<bool(int, array<bool, maxA*maxN/2>&)> sure = [&](int node, array<bool, maxA*maxN/2>& possreferee){
        if(node == 0)return true;
        if(!possreferee[node])return false;
        for(int p:path[node]){
            if(isInStack[p])continue;
            isInStack[p] = true;
            bool res = sure(node-a[p], possreferee);
            isInStack[p] = false;
            if(res)
                return true;
        }
        return false;
    };
    for(int i=0; i<N; i++){
        if(already[a[i]] != i){
            duplicate++;
            continue;
        }
        int part = sum-a[i];
#ifdef DEBUG
        printf("---- %d : %d %d----\n", i, a[i], part);
#endif
        array<bool, maxN*maxA/2> correct = cache;
        isInStack[i] = true;
        for(int idw=1; idw<=part/2; idw++){
            if(cache[idw]){
#ifdef DEBUG
                printf("%d : ", idw);
#endif
                bool res = sure(idw, correct);
#ifdef DEBUG
                printf(" => %d", res);
#endif
                correct[idw] = res;
                if(correct[idw]){
#ifdef DEBUG
                    printf(" => %d", part-idw*2);
#endif
                    poss[part-idw*2]++;
                }
#ifdef DEBUG
                printf("\n");
#endif
            }
        }
        isInStack[i] = false;
        poss[part]++;
    }
    int count = 0;
    for(int i=0; i<sum; i++)
        count += poss[i] == N-duplicate;
    printf("%d\n", count);
    if(count){
        for(int i=0; i<sum; i++){
            if(poss[i] == N-duplicate){
                printf("%d ", i);
            }
        }
        printf("\n");
    }
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d\n", &N);
      |     ~~~~~^~~~~~~~~~~~
bootfall.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

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