1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <array>
#include <tuple>
using namespace std;

typedef tuple<unsigned, unsigned, unsigned> potwor;

unsigned long long zyskowne(vector<potwor>&, const unsigned);
bool stratne(vector<potwor>&, const unsigned long long);

int main() {
  ios_base::sync_with_stdio(false);
  unsigned n, z;
  cin >> n >> z;
  vector<unsigned> pobrane; pobrane.reserve(2*n);
  copy(istream_iterator<unsigned>(cin), istream_iterator<unsigned>(),
       back_inserter(pobrane));
  array<vector<potwor>, 2> worki;
  for(unsigned i = 0; i < n; ++i) {
    const auto d = pobrane[2*i], a = pobrane[2*i+1];
    worki[d>a].emplace_back(d, a, i + 1);
   }
  unsigned long long najwiecej_zycia = zyskowne(worki[0], z);
  if(najwiecej_zycia == 0ULL || !stratne(worki[1], najwiecej_zycia)) {
    cout << "NIE\n";
    return 0;
   }
  cout << "TAK\n";
  transform(begin(worki[0]), end(worki[0]), ostream_iterator<unsigned>(cout, " "),
            [](potwor x){return get<2>(x);});
  transform(begin(worki[1]), end(worki[1]), ostream_iterator<unsigned>(cout, " "),
            [](potwor x){return get<2>(x);});
  cout << '\n';
 }

unsigned long long zyskowne(vector<potwor>& instancje, const unsigned z) {
  sort(begin(instancje), end(instancje), [](potwor a, potwor b){return get<0>(a) < get<0>(b);});
  unsigned long long zycie = z;
  for(const auto& x : instancje) {
    if(zycie <= get<0>(x))
     return 0;
    zycie += get<1>(x) - get<0>(x);
   }
  return zycie;
 }

bool stratne(vector<potwor>& instancje, const unsigned long long zycie) {
  sort(begin(instancje), end(instancje), [](potwor a, potwor b){return get<1>(a) > get<1>(b);});
  unsigned long long utracone = 0;
  for(const auto& x : instancje) {
    if(utracone + get<0>(x) >= zycie)
     return false;
    utracone += get<0>(x) - get<1>(x);
   }
  return true;
 }