結果

問題 No.15 カタログショッピング
コンテスト
ユーザー yaoshimax
提出日時 2015-02-10 18:13:58
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 31 ms / 5,000 ms
コード長 2,037 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,000 ms
コンパイル使用メモリ 134,512 KB
実行使用メモリ 11,120 KB
最終ジャッジ日時 2026-03-08 22:11:04
合計ジャッジ時間 1,631 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;
int main(){
  int N,S;
  scanf("%d%d",&N,&S);
  int P[N];
  for( int i = 0 ; i <N; i++) scanf("%d", &P[i]);
  vector< pair<int,vector<int> > > p1;
  vector< pair<int,vector<int> > > p2;
  
  for( int i = 0 ; i < (1<<(N/2)); i++ ){
    vector<int> v;
    int sum =0;
    for( int j = 0 ; j < (N/2); j++){
      if( (i&(1<<j))!=0 ){
        v.push_back(j);
        sum+=P[j];
      }
    }
    p1.push_back(make_pair(sum,v));
  }
  for( int i = 0 ; i < (1<<(N-N/2)) ; i++ ){
    vector<int> v;
    int sum =0;
    for( int j = 0 ; j < (N-N/2); j++){
      if( (i&(1<<j))!=0 ){
        v.push_back(N/2+j);
        sum+=P[N/2+j];
      }
    }
    p2.push_back(make_pair(sum,v));
  }
  sort( p2.begin(),p2.end());
  vector< vector<int> > ans;
  for( int i = 0 ; i <(int) p1.size(); i++ ){
    int cost = p1[i].first;
    if( S-cost < 0 ) continue;
    int left = 0;
    int right = p2.size();
    while( left < right ){
      int mid = (left+right)/2;
      if( p2[mid].first < S-cost ){
        left=mid+1;
      }
      else{
        right=mid;
      }
    }
    //cout << cost << ", "<< left <<endl;
    while( left<(int)p2.size() && p2[left].first==S-cost){
      vector<int> ansvec;
      for(int j = 0 ; j < (int)p1[i].second.size(); j++ ){
        ansvec.push_back(p1[i].second[j]);
      }
      for(int j = 0 ; j < (int)p2[left].second.size(); j++ ){
        ansvec.push_back(p2[left].second[j]);
      }
      ans.push_back(ansvec);
      left++;
    }
  }

  sort(ans.begin(),ans.end());
  for( int i = 0 ; i < (int)ans.size(); i++){
    for( int j = 0 ; j < (int)ans[i].size(); j++ ){
      cout << 1+ans[i][j]<<" ";
    }
    cout << endl;
  }
  return 0;
}
0