Advertisement
Guest User

Untitled

a guest
Feb 11th, 2016
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.84 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:16777216")
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. #include <list>
  7. #include <iterator>
  8. #include <cassert>
  9. #include <set>
  10. #include <queue>
  11. #include <iostream>
  12. #include <sstream>
  13. #include <stack>
  14. #include <deque>
  15. #include <cmath>
  16. #include <memory.h>
  17. #include <cstdlib>
  18. #include <cstdio>
  19. #include <cctype>
  20. #include <algorithm>
  21. #include <utility>
  22. #include <time.h>
  23. #include <complex>
  24. using namespace std;
  25.  
  26. #define FOR(i, a, b) for(int i=(a);i<(b);i++)
  27. #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
  28. #define FILL(A,value) memset(A,value,sizeof(A))
  29.  
  30. #define ALL(V) V.begin(), V.end()
  31. #define SZ(V) (int)V.size()
  32. #define PB push_back
  33. #define MP make_pair
  34. #define Pi 3.14159265358979
  35. #define x0 ikjnrmthklmnt
  36. #define y0 lkrjhkltr
  37. #define y1 ewrgrg
  38.  
  39. typedef long long Int;
  40. typedef unsigned long long UInt;
  41. typedef vector<int> VI;
  42. typedef pair<int, int> PII;
  43. typedef pair<Int, Int> PLL;
  44. typedef pair<double, double> PDD;
  45. typedef complex<double> base;
  46.  
  47. const int INF = 1000000000;
  48. const int BASE = 1000000000;
  49. const int MAX = 107;
  50. const int MAX2 = 7777;
  51. const int MAXE = 100000;
  52. const int ADD = 1000000;
  53. const int MOD = 1000000007;
  54. const int CNT = 800;
  55.  
  56. vector<int> W;
  57.  
  58.  
  59. int n , m , k , t , c;
  60. int p;
  61.  
  62. struct Shop
  63. {
  64. int x , y;
  65. vector<int> a;
  66. friend istream & operator>>(istream & in, Shop & s)
  67. {
  68. in >> s.x >> s.y;
  69. s.a.resize(p);
  70. FOR(i,0,p)
  71. {
  72. in >> s.a[i];
  73. }
  74. return in;
  75. }
  76. };
  77.  
  78. struct Order
  79. {
  80. int x , y;
  81. int id;
  82. vector<int> p;
  83. friend istream & operator>>(istream & in, Order & o)
  84. {
  85. in >> o.x >> o.y;
  86. int t;
  87. in >> t;
  88. FOR(i,0,t)
  89. {
  90. int x;
  91. in >> x;
  92. o.p.push_back(x);
  93. }
  94. return in;
  95. }
  96.  
  97. int TotalWeight()
  98. {
  99. int r = 0;
  100. FOR(i,0,p.size())
  101. {
  102. r += W[p[i]];
  103. }
  104. return r;
  105. }
  106. };
  107.  
  108. vector<Shop> S;
  109. vector<Order> O;
  110.  
  111. int Sqrt(int x)
  112. {
  113. int y = sqrt(1.0 * x);
  114. while (y * y < x) ++y;
  115. return y;
  116. }
  117.  
  118. int dist(int x1, int y1 , int x2 , int y2)
  119. {
  120. return Sqrt( (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) );
  121. }
  122.  
  123. bool Comp(Order & a , Order & b)
  124. {
  125. int t1 = dist(a.x , a.y , S[0].x , S[0].y) + a.p.size();
  126. int t2 = dist(b.x , b.y , S[0].x , S[0].y) + b.p.size();
  127. int c1 = (a.TotalWeight() + c - 1) / c;
  128. int c2 = (b.TotalWeight() + c - 1) / c;
  129. return MP(c1 , t1) < MP(c2 , t2);
  130. }
  131.  
  132. struct Command
  133. {
  134. int drone;
  135. char ch;
  136. int a , b , c;
  137. Command() {}
  138. Command(int _d, char _ch, int _a, int _b, int _c)
  139. {
  140. drone = _d;
  141. ch = _ch;
  142. a = _a;
  143. b = _b;
  144. c = _c;
  145. }
  146.  
  147. friend ostream & operator<<(ostream & out , const Command & cmd)
  148. {
  149. out << cmd.drone << ' ' << cmd.ch << ' ' << cmd.a << ' ' << cmd.b << ' ' << cmd.c;
  150. return out;
  151. }
  152. };
  153.  
  154. vector<Command> res;
  155.  
  156. set<PII> Drones;
  157.  
  158. int curTime;
  159.  
  160. bool RunCommand(int time , int drone, int order, vector<int> & p)
  161. {
  162. int tt = dist(S[0].x , S[0].y , O[order].x , O[order].y) + 2 * p.size();
  163.  
  164. bool ok = 1;
  165. FOR(i,0,p.size())
  166. {
  167. S[0].a[p[i]]--;
  168. if (S[0].a[p[i]] < 0)
  169. {
  170. ok = 0;
  171. }
  172. }
  173.  
  174. if (time + tt > t) ok = 0;
  175.  
  176. if (!ok)
  177. {
  178. FOR(i,0,p.size())
  179. {
  180. S[0].a[p[i]]++;
  181. }
  182. }
  183.  
  184. if (ok)
  185. {
  186. for(int i = 0; i < p.size(); ++i)
  187. {
  188. res.push_back(Command(drone , 'L', 0, p[i], 1));
  189. }
  190. for(int i = 0; i < p.size(); ++i)
  191. {
  192. res.push_back(Command(drone , 'D', order, p[i], 1));
  193. }
  194. curTime = time + tt;
  195. Drones.insert( MP( time + tt + dist(S[0].x , S[0].y , O[order].x , O[order].y) , drone) );
  196. return 1;
  197. }
  198. else
  199. {
  200. Drones.insert(MP(time, drone));
  201. return 0;
  202. }
  203. }
  204.  
  205. int main()
  206. {
  207. freopen("in.txt", "r", stdin);
  208. //freopen("distance.in", "r", stdin);
  209. //freopen("distance.out", "w", stdout);
  210. freopen("out.txt" , "w" , stdout);
  211.  
  212. cin >> n >> m >> k >> t >> c;
  213.  
  214.  
  215. cin >> p;
  216. W.resize(p);
  217. FOR(i,0,p)
  218. {
  219. cin >> W[i];
  220. }
  221.  
  222. int s;
  223. cin >> s;
  224. S.resize(s);
  225. FOR(i,0,s)
  226. {
  227. cin >> S[i];
  228. }
  229.  
  230. int o;
  231. cin >> o;
  232. O.resize(o);
  233. FOR(i,0,o)
  234. {
  235. cin >> O[i];
  236. O[i].id = i;
  237. }
  238.  
  239. sort(ALL(O), Comp);
  240.  
  241. int score = 0;
  242.  
  243. FOR(i,0,k)
  244. {
  245. Drones.insert(MP(0, i));
  246. }
  247.  
  248. for(int i = 0; i < O.size(); ++i)
  249. {
  250. vector<VI> A;
  251. random_shuffle(ALL(O[i].p));
  252. int curw = 0;
  253. VI B;
  254. FOR(j,0,O[i].p.size())
  255. {
  256. if (curw + W[O[i].p[j]] > c)
  257. {
  258. A.push_back(B);
  259. B.clear();
  260. B.push_back(W[O[i].p[j]]);
  261. curw = W[O[i].p[j]];
  262. }
  263. else
  264. {
  265. B.push_back(W[O[i].p[j]]);
  266. curw += W[O[i].p[j]];
  267. }
  268. }
  269. A.push_back(B);
  270. bool ok = 1;
  271. FOR(j,0,A.size())
  272. {
  273. PII d = *Drones.begin();
  274. Drones.erase(Drones.begin());
  275. ok &= RunCommand(d.first , d.second, O[i].id, A[j]);
  276. if (!ok) break;
  277. }
  278. if (ok)
  279. {
  280. score += (100 * (t - curTime) + t - 1) / t;
  281. }
  282. }
  283.  
  284. cout << res.size() << endl;
  285. FOR(i,0,res.size())
  286. {
  287. cout << res[i] << endl;
  288. }
  289.  
  290. cerr << score << endl;
  291.  
  292. return 0;
  293. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement