제출 #1368005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368005		jbn8	Bootfall (IZhO17_bootfall)	C++20	100 / 100	245 ms	3108 KiB

bootfall

#include <cstdio>
#include <array>
#include <cassert>
using namespace std;

const int maxN = 500;
const int maxA = 501;
using posstype = array<bool, maxA*maxN/2>;

constexpr int ilog2(int n){
    return 31^__builtin_clz(n);
}

constexpr int ilog2c(int n){
    return ilog2(n)+!!(n&(n-1));
}

array<posstype, ilog2(maxN)+2> logCache{};
array<int, ilog2(maxN)+2> logIndex{};
int N, sum;
array<int, maxN+1> a{};

template<bool different>
void calc(posstype& possout, const posstype& possin, int add){
    //printf("+%d\n", add);
    if constexpr(different)
        for(int j=0; j <= sum/2; j++){
            possout[j] = possin[j];
        }
    for(int j=sum/2-add; j >= 0; j--){
        if(possin[j]){
            possout[j+add] = true;
        }
    }
}

void calcrange(posstype& possout, const posstype& possin, int idfirst, int idend){
    //printf("%d -> %d\n", idfirst, idend);
    calc<true>(possout, possin, a[idfirst]);
    for(int idp=idfirst+1; idp<idend; idp++){
        calc<false>(possout, possout, a[idp]);
    }
}


void recalcLog(int startLevel, int start){
    //printf("%d\n", startLevel);
    int curend = logIndex[startLevel-1];
    assert(curend >= start);
    assert(startLevel >= 1 && startLevel <= ilog2(N)+1);
    for(int level = startLevel; level <= ilog2(N)+1; level++){
        int shift = ilog2(N)+1-level;
        int block = 1 << shift;
        if(block+start > curend){
            logCache[level] = logCache[level-1];
        }else{
            calcrange(logCache[level], logCache[level-1], curend-block, curend);
            curend -= block;
        }
        logIndex[level] = curend;
    }
    assert(curend == start);
}
void addToLog(int add){
    for(int i=0; i<=ilog2(N)+1; i++){
        calc<false>(logCache[i], logCache[i], add);
    }
}

int main(){
    scanf("%d\n", &N);
    array<bool, maxA> already{};
    sum = 0;
    for(int i=0; i<N; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    array<int, maxA*maxN> poss{};
    logCache[0][0] = true;
    logIndex[0] = N;
    recalcLog(1, 0);
    if(!logCache[ilog2(N)+1][sum/2]){
        printf("0\n");
        return 0;
    }
    int duplicate = 0;
    for(int i=0; i<N; i++){
        int part = sum-a[i];
        if(already[a[i]]){
            addToLog(a[i-1]);
            duplicate++;
            continue;
        }
#ifdef DEBUG
        printf(" ------- %d(%d) ------ \n", i, a[i]);
#endif
        already[a[i]] = true;
        int startLevel = ilog2(N)+1;
        while(logIndex[startLevel] < i+1){
            startLevel--;
        }
        startLevel++;
#ifdef DEBUG
        printf("level: %d/%d\n", startLevel, ilog2(N)+1);
#endif
        if(startLevel <= ilog2(N)+1)
            recalcLog(startLevel, i+1);
        if(i)
            addToLog(a[i-1]);
        posstype& possreferee = logCache[ilog2(N)+1];
        for(int idw=0; idw<=part/2; idw++){
            if(possreferee[idw]){
#ifdef DEBUG
                printf("%d/%d => %d\n", idw, part/2, part-idw*2);
#endif
                poss[part-idw*2]++;
            }
        }
    }
    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");
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

• 서브태스크 1: 6 / 6
• 서브태스크 2: 7 / 7
• 서브태스크 3: 15 / 15
• 서브태스크 4: 16 / 16
• 서브태스크 5: 21 / 21
• 서브태스크 6: 35 / 35