結果

問題 No.15 カタログショッピング
ユーザー たこしたこし
提出日時 2015-06-12 18:34:43
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,400 bytes
コンパイル時間 1,332 ms
コンパイル使用メモリ 113,532 KB
実行使用メモリ 10,888 KB
最終ジャッジ日時 2023-09-20 21:04:44
合計ジャッジ時間 2,599 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 131 ms
10,888 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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