weight1.pas 1.6 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
  1. program hxy;
  2. Const maxn=1000;
  3. maxw=1000000;
  4. infile='weight.in';
  5. outfile='weight.out';
  6. Var a:array[1..2*maxn]of longint;
  7. w:array[1..maxw]of integer;
  8. Ans:array[0..maxn]of longint;
  9. n,m,Tot,nw:longint;
  10. procedure Qsort(x,y:longint);
  11. var xx,yy,k:longint;
  12. begin
  13. if x>=y then exit;
  14. xx:=x; yy:=y; k:=a[x];
  15. repeat
  16. while (xx<yy) and (k<=a[yy]) do dec(yy);
  17. if xx<yy then a[xx]:=a[yy];
  18. while (xx<yy) and (k>=a[xx]) do inc(xx);
  19. if xx<yy then a[yy]:=a[xx];
  20. until xx=yy;
  21. a[xx]:=k;
  22. Qsort(x,xx-1);
  23. Qsort(xx+1,y);
  24. end;
  25. procedure Getnew;
  26. var i,j:longint;
  27. begin
  28. j:=1;
  29. for i:=2 to m do
  30. if a[i]>a[j] then
  31. begin
  32. inc(j);
  33. a[j]:=a[i];
  34. end;
  35. m:=j;
  36. end;
  37. procedure DataIn;
  38. var i,j:longint;
  39. begin
  40. fillchar(w,sizeof(w),0);
  41. w[0]:=2;
  42. Tot:=0;
  43. readln(n,m);
  44. for i:=1 to m do read(a[i]);
  45. readln;
  46. Qsort(1,m);
  47. GeTnew;
  48. for i:=1 to 2*n do
  49. begin
  50. read(j); inc(w[j]);
  51. if j>Tot then Tot:=j;
  52. end;
  53. readln;
  54. nw:=0;
  55. end;
  56. procedure OutAns;
  57. var i,j:longint;
  58. begin
  59. assign(output,outfile);
  60. rewrite(output);
  61. for i:=1 to n-1 do write(Ans[i],' ');
  62. writeln(Ans[n]);
  63. close(output);
  64. end;
  65. procedure Try(x:longint);
  66. var i,j,k,step:longint;
  67. begin
  68. if x>n then begin
  69. OutAns;
  70. halt;
  71. end;
  72. for i:=1 to m do
  73. if (w[nw+a[i]]>0) and (w[Tot-nw-a[i]]>0) then
  74. begin
  75. dec(w[nw+a[i]]);
  76. dec(w[Tot-nw-a[i]]);
  77. inc(nw,a[i]);
  78. Ans[x]:=a[i];
  79. Try(x+1);
  80. dec(nw,a[i]);
  81. inc(w[nw+a[i]]);
  82. inc(w[Tot-nw-a[i]]);
  83. end;
  84. end;
  85. begin
  86. assign(input,infile);
  87. reset(input);
  88. DataIn;
  89. nw:=0;
  90. Try(1);
  91. close(input);
  92. end.