Назад к лучшим решениям Status: AC, problem ZRIS, contest ZEL06. By natalia (Natalia Bondarenko), 2006-03-02 13:19:00.
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. #define forn(i, n) for(int i = 0; i < int(n); i++)
  7. #define all(x) x.begin(), x.end()
  8.  
  9. #define NMAX 1003
  10. #define KMAX 100005
  11. #define INF 1000006
  12. #define limit 45000
  13.  
  14. #define IN_FILE "input.txt"
  15. #define OUT_FILE "output.txt"
  16.  
  17. int n, k;
  18.  
  19. struct TRect
  20. {
  21. int w, h, l;
  22. } r[KMAX];
  23.  
  24.  
  25. bool Comp(const TRect &a, const TRect &b)
  26. {
  27. return (a.w * a.h > b.w * b.h || (a.w * a.h == b.w * b.h && (a.w > b.w || (a.w == b.w && (a.h > b.h)))));
  28. }
  29.  
  30. bool Comp2(const TRect &a, const TRect &b)
  31. {
  32. return (a.w > b.w || (a.w == b.w && (a.h > b.h)));
  33. }
  34.  
  35. int a[NMAX][2*NMAX];
  36.  
  37. struct TAns
  38. {
  39. int x1, y1, x2, y2, num;
  40. };
  41.  
  42. vector <TAns> ans, v;
  43. int ans_s;
  44.  
  45. inline void FillBlock1(int lx, int ly, int rx, int ry)
  46. {
  47. for(int i = lx; i < rx; i++)
  48. {
  49. a[i][ly << 1] = ry;
  50. a[i][(ry << 1) - 1] = 1;
  51. }
  52. }
  53. inline void FillBlock0(int lx, int ly, int rx, int ry)
  54. {
  55. for(int i = lx; i < rx; i++)
  56. {
  57. a[i][ly << 1] = 0;
  58. a[i][(ry << 1) - 1] = 0;
  59. }
  60. }
  61.  
  62. int t;
  63.  
  64. void Rec(int x, int y, int l, int s, int max_free)
  65. {
  66. ++t;
  67. if (ans_s == 0)
  68. {
  69. return;
  70. }
  71. if (s < ans_s)
  72. {
  73. ans_s = s;
  74. ans.resize(v.size());
  75. copy(all(v), ans.begin());
  76. }
  77.  
  78. if (t > limit)
  79. {
  80. return;
  81. }
  82. if (max_free == y)
  83. {
  84. max_free = -1;
  85. }
  86. if (y >= n)
  87. {
  88. y = 0;
  89. ++x;
  90. }
  91. while (x < n && a[x][y << 1] > 0)
  92. {
  93. y = a[x][y << 1];
  94. if (y >= n)
  95. {
  96. ++x; y = 0;
  97. }
  98. }
  99.  
  100. while (l < k && (r[l].h * r[l].w > s || r[l].l == 0))
  101. {
  102. ++l;
  103. }
  104. if (x >= n || l >= k)
  105. {
  106. return;
  107. }
  108.  
  109. if (max_free == -1)
  110. {
  111. max_free = y;
  112. while (max_free < n && a[x][max_free << 1] == 0)
  113. {
  114. ++max_free;
  115. }
  116. }
  117.  
  118. TAns q;
  119. q.x1 = x+1; q.y1 = y+1;
  120.  
  121. for(int i = l; i < k; i++)
  122. {
  123. if (r[i].l > 0 && x + r[i].h <= n && y + r[i].w <= max_free)
  124. {
  125. q.x2 = x + r[i].h; q.y2 = y + r[i].w;
  126. q.num = i;
  127. v.push_back(q);
  128. --r[i].l;
  129. FillBlock1(x, y, x + r[i].h, y + r[i].w);
  130. Rec(x, y + r[i].w, l, s - r[i].h * r[i].w, max_free);
  131. if (t > limit)
  132. {
  133. return;
  134. }
  135. FillBlock0(x, y, x + r[i].h, y + r[i].w);
  136. ++r[i].l;
  137. v.pop_back();
  138. }
  139. if (r[i].w != r[i].h && r[i].l > 0 && x + r[i].w <= n && y + r[i].h <= max_free)
  140. {
  141. q.x2 = x + r[i].w; q.y2 = y + r[i].h;
  142. q.num = i;
  143. v.push_back(q);
  144. --r[i].l;
  145. FillBlock1(x, y, x + r[i].w, y + r[i].h);
  146. Rec(x, y + r[i].h, l, s - r[i].w * r[i].h, max_free);
  147. if (t > limit)
  148. {
  149. return;
  150. }
  151. FillBlock0(x, y, x + r[i].w, y + r[i].h);
  152. ++r[i].l;
  153. v.pop_back();
  154. }
  155. }
  156. }
  157.  
  158. struct TColon
  159. {
  160. int h, w, l, r;
  161. };
  162.  
  163. TColon col, next;
  164.  
  165. int main()
  166. {
  167. int test; scanf("%d", &test);
  168. forn(run, test)
  169. {
  170. scanf("%d %d", &n, &k);
  171. forn(i, k)
  172. {
  173. scanf("%d %d %d", &r[i].w, &r[i].h, &r[i].l);
  174. if (r[i].w < r[i].h)
  175. {
  176. swap(r[i].w, r[i].h);
  177. }
  178. }
  179.  
  180. if (n <= 200)
  181. {
  182. sort(r, r + k, Comp);
  183. v.clear();
  184. ans.clear(); ans_s = INF;
  185. forn(i, n)
  186. {
  187. forn(j, 2*n)
  188. {
  189. a[i][j] = 0;
  190. }
  191. }
  192. t = 0;
  193. Rec(0, 0, 0, n*n, n);
  194. }
  195. else
  196. {
  197. ans.clear();
  198. sort(r, r + k, Comp2);
  199.  
  200. col.h = n;
  201. col.w = n;
  202. col.l = 0;
  203. col.r = 0;
  204. while (true)
  205. {
  206. if (col.w == 0)
  207. {
  208. break;
  209. }
  210. bool flag = false;
  211. forn(i, k)
  212. {
  213. if (r[i].l > 0 && r[i].w <= col.w && r[i].h <= col.h)
  214. {
  215. TAns q;
  216. q.x1 = col.l+1;
  217. q.y1 = col.r+1;
  218. q.x2 = col.l + r[i].w;
  219. q.y2 = col.r + r[i].h;
  220. --r[i].l;
  221. ans.push_back(q);
  222. col.r = q.y2;
  223. col.h -= r[i].h;
  224. if (!flag)
  225. {
  226. flag = true;
  227. next.l = q.x2;
  228. next.r = 0;
  229. next.h = n;
  230. next.w = n - q.x2;
  231. }
  232. if (col.h == 0)
  233. {
  234. break;
  235. }
  236. }
  237. }
  238. if (!flag)
  239. {
  240. break;
  241. }
  242. col = next;
  243. }
  244. }
  245. printf("%d\n", ans.size());
  246. forn(i, ans.size())
  247. {
  248. printf("%d %d %d %d\n", ans[i].x1, ans[i].y1, ans[i].x2, ans[i].y2);
  249. }
  250. }
  251.  
  252. return 0;
  253. }