結果

問題 No.15 カタログショッピング
コンテスト
ユーザー たこし
提出日時 2015-06-12 18:34:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,400 bytes
記録
コンパイル時間 1,287 ms
コンパイル使用メモリ 114,584 KB
実行使用メモリ 10,912 KB
最終ジャッジ日時 2024-07-06 15:52:48
合計ジャッジ時間 2,449 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF_MIN 100000000
#define INF 1145141919
#define INF_MAX 2147483647
#define LL_MAX 9223372036854775807
#define EPS 1e-10
#define PI acos(-1)
#define LL long long

using namespace std;

#define MAX_N 31

int N;
LL S;
LL P[MAX_N];

//値,文字列　
typedef pair<LL, string> PP;

vector<PP> Left, Right;

int main(){

  cin >> N >> S;
  for(int i = 0; i < N; i++){
    cin >> P[i];
  }

  //左側半分列挙
  for(int i = 0; i < (1 << N/2); i++){
    
    stringstream ss;
    LL ret = 0;

    for(int j = 0; j < N/2; j++){
      if((i >> j) & 1){
	ss << j + 1 << " ";
	ret += P[j];
      }
    }
    
    Left.push_back(PP(ret, ss.str()));

  }

  //右側半分列挙
  for(int i = 0; i < (1 << (N+1)/2); i++){
    
    stringstream ss;
    LL ret = 0;
    
    for(int j = N/2; j < N; j++){
      if((i >> (j-N/2)) & 1){
	ss << j + 1 << " ";
	ret += P[j];
      }
    }

    Right.push_back(PP(ret, ss.str()));

  }

  sort(Left.begin(), Left.end());
  sort(Right.begin(), Right.end());

  /* デバッグ
  printf("Left\n");
  for(int i = 0; i < Left.size(); i++){
    printf("%s%lld\n", Left[i].second.c_str(), Left[i].first);
  }
  printf("Right\n");
  for(int i = 0; i < Right.size(); i++){
    printf("%s%lld\n", Right[i].second.c_str(), Right[i].first);
  }
  */

  vector<string> ans_List;

  //にぶたん
  for(int l = 0; l < Left.size(); l++){
    
    string tmp = "";
    LL tmpS = S - Left[l].first;

    int lr = lower_bound(Right.begin(), Right.end(), PP(tmpS,tmp)) - Right.begin();

    int rr = lower_bound(Right.begin(), Right.end(), PP(tmpS+1,tmp)) - Right.begin();

    while(lr < rr){

      ans_List.push_back(Left[l].second + Right[lr].second);

      lr++;

    }

  }

  for(int i = 0; i < ans_List.size(); i++){
    ans_List[i] = ans_List[i].substr(0, ans_List[i].length() - 1);
  }

  sort(ans_List.begin(), ans_List.end());

  for(int i = 0; i < ans_List.size(); i++){
    cout << ans_List[i] << endl;
  }

  return 0;

}
0