結果

問題 No.15 カタログショッピング
コンテスト
ユーザー tottoripaper
提出日時 2014-11-16 07:03:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,918 bytes
コンパイル時間 1,931 ms
コンパイル使用メモリ 39,000 KB
最終ジャッジ日時 2024-11-14 18:55:28
合計ジャッジ時間 2,334 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:66:42: error: ‘greater’ is not a member of ‘std’
   66 |     std::sort(v3.begin(), v3.end(), std::greater<int>());
      |                                          ^~~~~~~
main.cpp:66:50: error: expected primary-expression before ‘int’
   66 |     std::sort(v3.begin(), v3.end(), std::greater<int>());
      |                                                  ^~~
main.cpp:11:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   11 |     scanf("%d %d", &N, &S);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:13:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 |     for(int i=0;i<N;i++){scanf("%d", ps+i);}
      |                          ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <algorithm>
#include <vector>

typedef std::pair<int,int> P;

int N, S;
int ps[31];

int main(){
    scanf("%d %d", &N, &S);

    for(int i=0;i<N;i++){scanf("%d", ps+i);}
    std::reverse(ps, ps+N);

    std::vector<P> v1, v2;
    for(int i=0;i<(1<<(N/2));i++){
        int sum = 0;
        for(int j=0;j<N/2;j++){
            if(i >> j & 1){
                sum += ps[j];
            }
        }

        if(sum > S){continue;}
        v1.push_back(std::make_pair(sum, i));
    }
    std::sort(v1.begin(), v1.end());

    // for(auto p : v1){printf("v1: %d, %d\n", p.first, p.second);}

    for(int i=0;i<1<<((N+1)/2);i++){
        int i_ = i << (N/2), sum = 0;
        for(int j=N/2;j<N;j++){
            if(i_ >> j & 1){
                sum += ps[j];
            }
        }

        if(sum > S){continue;}
        v2.push_back(std::make_pair(sum, i_));
    }
    std::sort(v2.begin(), v2.end());

    // for(auto p : v2){printf("v2: %d, %d\n", p.first, p.second);}

    std::vector<int> v3;
    int v1_size = v1.size(), v2_size = v2.size();
    for(int i=(int)v1.size()-1,j=0;i>=0;i--){
        P p = v1[i];
        while(j < v2_size && p.first + v2[j].first < S){j += 1;}
        
        int k = j;
        while(j < v2_size && p.first + v2[j].first == S){
            int state = p.second + v2[j].second;
            v3.push_back(state);

            j += 1;
        }

        if(i > 0 && v1[i-1].first == p.first){
            j = k;
        }
    }

    std::sort(v3.begin(), v3.end(), std::greater<int>());
    for(auto state : v3){
        for(int k=N-1;k>=0;k--){
            if((state >> k & 1) == 0){continue;}
                
            if((1 << k) == (state & -state)){
                printf("%d\n", N-k);
            }else{
                printf("%d ", N-k);
            }
        }
    }
}
0