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
60
program bohater; //runda 2B           13.05.2014
const nmax=100000;
type Ti=longint;
  Tpot = record d,a,klucz,nrpot:Ti end;
  Tabpot = array[1..nmax] of Tpot;
var n,i,d1,a1,dmax,amax,nrw:Ti;
  z,dsum,asum: qword; //sumy:di,ai
  potd,pota: Tabpot;//dodatnie i ujemne różnice a-d
  rozw: array[1..nmax] of Ti;//kolejność toczenia walk

Procedure MSort(n:Ti; Var Tab:Tabpot);
 Var Le,Ra: Array[1..nmax div 2 +1] of Tpot;//pom
{.}Procedure Merge(p,q,r:Ti); Var n1,n2,i,j,k:Ti;
   Begin n1:=q-p+1; n2:=r-q;
   for i:=1 to n1 do Le[i]:=Tab[p+i-1];
   for j:=1 to n2 do Ra[j]:=Tab[q+j];
   Le[n1+1].klucz:=-1;{wartownik} Ra[n2+1].klucz:=-1; i:=1; j:=1;
   for k:=p to r do  if Le[i].klucz>=Ra[j].klucz then
    Begin Tab[k]:=Le[i]; Inc(i) End else Begin Tab[k]:=Ra[j]; Inc(j) End
{-}End;{Merge}
{.}Procedure S(p,r:Ti); Var q:Ti;
   Begin if p<r then Begin q:=(p+r)div 2;S(p,q);S(q+1,r);Merge(p,q,r)End
{.}End;{S}
Begin S(1,n) End;{Msort}

begin  dsum:=0; asum:=0; dmax:=0; amax:=0;//zakresy tablic potd, pota
  readln(n,z);//dane
  for i:=1 to n do
  begin  readln(d1,a1); dsum+=d1; asum+=a1;
    if d1<=a1 then  with pota[amax+1] do
      begin d:=d1; a:=a1; klucz:=d1; nrpot:=i; amax+=1 end
    else   with potd[dmax+1] do
      begin d:=d1; a:=a1; klucz:=a1; nrpot:=i; dmax+=1 end;
    if z+asum<=dsum then begin writeln('NIE'); exit end
  end;//czyt dane

 //Etap 1 - nabieranie sił przez bohatera
  Msort(amax,pota);
  nrw:=0;//aktualnie nr walki
  for i:=amax downto 1 do  with pota[i] do
  if z>d then
  begin
    z+=a-d; nrw+=1; rozw[nrw]:=nrpot
  end
  else begin writeln('NIE'); exit end; 

// Etap 2 - pozostałe walki
  Msort(dmax,potd);
  for i:=1 to dmax do  with potd[i] do
  if z>d then
  begin
    z+=a-d; nrw+=1; rozw[nrw]:=nrpot
  end
  else begin writeln('NIE'); exit end;

//wyniki
  writeln('TAK');
  for i:=1 to n-1 do write(rozw[i],' ');
  writeln(rozw[n])
end.