Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 17.18 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <sstream>
  7. #include <fstream>
  8. #include <stdint.h>
  9. #include <string.h>
  10.  
  11. #define _USE_MATH_DEFINES
  12. #include <math.h>
  13.  
  14. #include <vector>
  15. #include <list>
  16. #include <set>
  17. #include <map>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20. #include <queue>
  21. #include <stack>
  22. #include <deque>
  23. #include <string>
  24.  
  25. #include <algorithm>
  26. #include <functional>
  27. #include <bitset>
  28. #include <functional>
  29. #include <chrono>
  30. #include <random>
  31.  
  32. #define sqr(x) (x) * (x)
  33.  
  34. typedef unsigned int u32;
  35. typedef int i32;
  36. typedef unsigned long long int u64;
  37. typedef long long int i64;
  38. typedef uint16_t u16;
  39. typedef int16_t i16;
  40. typedef uint8_t u8;
  41. typedef int8_t i8;
  42.  
  43. using namespace std;
  44. using namespace std::chrono;
  45.  
  46. const i64 mod = 1000000007ll;
  47. const i64 smod = 998244353ll;
  48. const i64 inf = 10000000000000007ll;
  49.  
  50. const double eps = 1e-10;
  51.  
  52. const i64 MAXN = 10004;
  53. const i64 MAXM = 1000001;
  54.  
  55. namespace ALL_THIS_SHIT {
  56.  
  57. struct World {
  58. int height, width;
  59. int dronesCount;
  60. int maxTime;
  61. int maxWeight;
  62.  
  63. int productsCount;
  64. int warehousesCount;
  65. int ordersCount;
  66. } world;
  67.  
  68.  
  69.  
  70. struct Product {
  71. int weight;
  72. };
  73. vector<Product> products;
  74.  
  75.  
  76.  
  77. struct Warehouse {
  78. int y, x;
  79. vector<int> productsCount;
  80. };
  81. vector<Warehouse> warehouses;
  82.  
  83.  
  84.  
  85. struct Order {
  86. int y, x;
  87. vector<int> productsCount;
  88. };
  89. vector<Order> orders;
  90.  
  91.  
  92.  
  93. struct Drone {
  94. int y, x;
  95. int time;
  96. int weight;
  97. vector<int> productsCount;
  98.  
  99. void moveTo(int ty, int tx) {
  100. double dy = y - ty;
  101. double dx = x - tx;
  102. double d = ceil(hypot(dx, dy));
  103.  
  104. y = ty;
  105. x = tx;
  106. time += d;
  107. }
  108. void moveToWarehouse(int i) {
  109. assert(0 <= i && i < world.warehousesCount);
  110. moveTo(warehouses[i].y, warehouses[i].x);
  111. }
  112. void moveToOrder(int i) {
  113. assert(0 <= i && i < world.ordersCount);
  114. moveTo(orders[i].y, orders[i].x);
  115. }
  116.  
  117. void wait(int waitTime) {
  118. assert(0 < waitTime);
  119. time += waitTime;
  120. }
  121. };
  122. vector<Drone> drones;
  123.  
  124.  
  125. struct Event {
  126. enum { UNLOAD, LOAD, DELIVER } type;
  127. int time;
  128. int droneIndex;
  129. int recipientIndex;
  130. int productIndex;
  131. int productAmount;
  132.  
  133. bool operator < (const Event &that) const {
  134. return tie(time, type) < tie(that.time, that.type);
  135. }
  136.  
  137. int process() {
  138. assert(0 <= droneIndex && droneIndex < world.dronesCount);
  139. Drone &drone = drones[droneIndex];
  140.  
  141. assert(0 <= productIndex && productIndex < world.productsCount);
  142. assert(0 < productAmount);
  143.  
  144. drone.time = time;
  145.  
  146. if (type == Event::UNLOAD) {
  147.  
  148. assert(0 <= recipientIndex && recipientIndex < world.warehousesCount);
  149. assert(drone.productsCount[productIndex] >= productAmount);
  150.  
  151. drone.time++;
  152. assert(drone.time < world.maxTime);
  153. drone.weight -= productAmount * products[productIndex].weight;
  154. drone.productsCount[productIndex] -= productAmount;
  155. warehouses[recipientIndex].productsCount[productIndex] += productAmount;
  156.  
  157. return 0;
  158.  
  159. }
  160.  
  161. if (type == Event::LOAD) {
  162.  
  163. assert(0 <= recipientIndex && recipientIndex < world.warehousesCount);
  164. assert(warehouses[recipientIndex].productsCount[productIndex] >= productAmount);
  165.  
  166. drone.time++;
  167. assert(drone.time < world.maxTime);
  168. drone.weight += productAmount * products[productIndex].weight;
  169. assert(drone.weight <= world.maxWeight);
  170. drone.productsCount[productIndex] += productAmount;
  171. warehouses[recipientIndex].productsCount[productIndex] -= productAmount;
  172.  
  173. return 0;
  174.  
  175. }
  176.  
  177. if (type == Event::DELIVER) {
  178.  
  179. assert(0 <= recipientIndex && recipientIndex < world.ordersCount);
  180. assert(drone.productsCount[productIndex] >= productAmount);
  181. assert(orders[recipientIndex].productsCount[productIndex] >= productAmount);
  182.  
  183. drone.time++;
  184. assert(drone.time < world.maxTime);
  185. drone.weight -= productAmount * products[productIndex].weight;
  186. drone.productsCount[productIndex] -= productAmount;
  187. orders[recipientIndex].productsCount[productIndex] -= productAmount;
  188.  
  189. if (*max_element(orders[recipientIndex].productsCount.begin(), orders[recipientIndex].productsCount.end()) == 0) {
  190. long long completionTime = drone.time;
  191. double score = (world.maxTime - completionTime);
  192. score /= world.maxTime;
  193. score *= 100;
  194. return ceil(score);
  195. }
  196.  
  197. return 0;
  198.  
  199. }
  200. }
  201. };
  202.  
  203. vector<Event> events;
  204.  
  205.  
  206.  
  207.  
  208.  
  209. void readInput(FILE *f) {
  210. fscanf(f, "%d%d", &world.height, &world.width);
  211. fscanf(f, "%d", &world.dronesCount);
  212. fscanf(f, "%d", &world.maxTime);
  213. fscanf(f, "%d", &world.maxWeight);
  214.  
  215. fscanf(f, "%d", &world.productsCount);
  216. products.resize(world.productsCount);
  217. for (int i = 0; i < world.productsCount; i++)
  218. fscanf(f, "%d", &products[i].weight);
  219.  
  220. fscanf(f, "%d", &world.warehousesCount);
  221. warehouses.resize(world.warehousesCount);
  222. for (int i = 0; i < world.warehousesCount; i++) {
  223. fscanf(f, "%d%d", &warehouses[i].y, &warehouses[i].x);
  224. warehouses[i].productsCount.resize(world.productsCount);
  225. for (int j = 0; j < world.productsCount; j++)
  226. fscanf(f, "%d", &warehouses[i].productsCount[j]);
  227. }
  228.  
  229. fscanf(f, "%d", &world.ordersCount);
  230. orders.resize(world.ordersCount);
  231. for (int i = 0; i < world.ordersCount; i++) {
  232. fscanf(f, "%d%d", &orders[i].y, &orders[i].x);
  233. orders[i].productsCount.resize(world.productsCount);
  234. int p;
  235. fscanf(f, "%d", &p);
  236. for (int j = 0; j < p; j++) {
  237. int x;
  238. fscanf(f, "%d", &x);
  239. orders[i].productsCount[x]++;
  240. }
  241. }
  242. }
  243.  
  244.  
  245.  
  246. void initializeDrones() {
  247. drones.resize(world.dronesCount);
  248. for (auto &drone : drones) {
  249. drone.y = warehouses[0].y;
  250. drone.x = warehouses[0].x;
  251. drone.time = 0;
  252. drone.weight = 0;
  253. drone.productsCount.resize(world.productsCount);
  254. }
  255. }
  256.  
  257.  
  258.  
  259. void readOutputAndMakeEvents(FILE *f) {
  260. int commandsCount;
  261. fscanf(f, "%d", &commandsCount);
  262. assert(0 <= commandsCount && commandsCount <= world.dronesCount * world.maxTime);
  263.  
  264. initializeDrones();
  265. events.clear();
  266.  
  267. for (int cmdI = 0; cmdI < commandsCount; cmdI++) {
  268. int droneIndex;
  269. char command;
  270. fscanf(f, "%d %c", &droneIndex, &command);
  271. assert(0 <= droneIndex && droneIndex < world.dronesCount);
  272.  
  273. if (command == 'L' || command == 'U') {
  274.  
  275. int warehouseIndex;
  276. fscanf(f, "%d", &warehouseIndex);
  277. assert(0 <= warehouseIndex && warehouseIndex < world.warehousesCount);
  278.  
  279. int productIndex;
  280. fscanf(f, "%d", &productIndex);
  281. assert(0 <= productIndex && productIndex < world.productsCount);
  282.  
  283. int productAmount;
  284. fscanf(f, "%d", &productAmount);
  285. assert(0 < productAmount);
  286.  
  287. drones[droneIndex].moveToWarehouse(warehouseIndex);
  288.  
  289. events.push_back({
  290. (command == 'L' ? Event::LOAD : Event::UNLOAD),
  291. drones[droneIndex].time,
  292. droneIndex,
  293. warehouseIndex,
  294. productIndex,
  295. productAmount
  296. });
  297.  
  298. } else if (command == 'D') {
  299.  
  300. int orderIndex;
  301. fscanf(f, "%d", &orderIndex);
  302. assert(0 <= orderIndex && orderIndex < world.ordersCount);
  303.  
  304. int productIndex;
  305. fscanf(f, "%d", &productIndex);
  306. assert(0 <= productIndex && productIndex < world.productsCount);
  307.  
  308. int productAmount;
  309. fscanf(f, "%d", &productAmount);
  310. assert(0 < productAmount);
  311.  
  312. drones[droneIndex].moveToOrder(orderIndex);
  313.  
  314. events.push_back({
  315. Event::DELIVER,
  316. drones[droneIndex].time,
  317. droneIndex,
  318. orderIndex,
  319. productIndex,
  320. productAmount
  321. });
  322.  
  323. } else if (command == 'W') {
  324.  
  325. int waitTime;
  326. fscanf(f, "%d", &waitTime);
  327. assert(0 < waitTime);
  328.  
  329. drones[droneIndex].wait(waitTime);
  330.  
  331. } else {
  332. assert(0);
  333. }
  334. }
  335.  
  336. }
  337.  
  338.  
  339.  
  340. int simulate(FILE *in, FILE *out) {
  341. readInput(in);
  342. readOutputAndMakeEvents(out);
  343. sort(events.begin(), events.end());
  344.  
  345. int totalScore = 0;
  346. for (auto &e : events) {
  347. totalScore += e.process();
  348. }
  349. return totalScore;
  350. }
  351. }
  352.  
  353.  
  354. i64 dist(pair<i64, i64> p1, pair<i64, i64> p2) {
  355. return (i64)ceil(sqrt(sqr(p1.first - p2.first) + sqr(p1.second - p2.second)));
  356. }
  357.  
  358. struct Product {
  359. i64 id;
  360. i64 w;
  361. };
  362.  
  363. struct Warehouse {
  364. i64 id;
  365. i64 x;
  366. i64 y;
  367. map<i64, i64> items;
  368. };
  369.  
  370. struct Order {
  371. i64 id;
  372. i64 x;
  373. i64 y;
  374.  
  375. vector<i64> wdist;
  376. vector<map<i64, i64>> split;
  377.  
  378. map<i64, i64> items;
  379. map<i64, i64> inflight;
  380. };
  381.  
  382. struct Action {
  383. i64 drone_id;
  384.  
  385. char t;
  386.  
  387. i64 order_id;
  388. i64 warehouse_id;
  389. i64 product_id;
  390. i64 cnt;
  391.  
  392. i64 wait;
  393. };
  394.  
  395. struct DroneState {
  396. i64 tm;
  397. i64 x;
  398. i64 y;
  399. };
  400.  
  401. struct Drone {
  402. i64 id;
  403. i64 x;
  404. i64 y;
  405. i64 tm;
  406. vector<Action> acts;
  407. vector<DroneState> states;
  408. };
  409.  
  410. i64 rows, columns, drones_count, deadline, max_load;
  411. i64 products_count, warehouses_count, orders_count;
  412.  
  413. vector<Product> products;
  414. vector<Warehouse> warehouses;
  415. vector<Order> orders;
  416. vector<Drone> drones;
  417.  
  418. vector<Action> actions;
  419.  
  420. void read_data(string fname) {
  421. fstream fs;
  422. fs.open(fname, fstream::in);
  423.  
  424. fs >> rows >> columns >> drones_count >> deadline >> max_load;
  425.  
  426. fs >> products_count;
  427. products.resize(products_count);
  428. for (i64 i = 0; i < products_count; i++) {
  429. products[i].id = i;
  430. fs >> products[i].w;
  431. }
  432.  
  433. fs >> warehouses_count;
  434. warehouses.resize(warehouses_count);
  435. for (i64 i = 0; i < warehouses_count; i++) {
  436. warehouses[i].id = i;
  437. fs >> warehouses[i].x >> warehouses[i].y;
  438.  
  439. for (i64 j = 0; j < products_count; j++) {
  440. i64 t;
  441. fs >> t;
  442. if (t > 0) {
  443. warehouses[i].items[j] = t;
  444. }
  445. }
  446. }
  447.  
  448. fs >> orders_count;
  449. orders.resize(orders_count);
  450. for (i64 i = 0; i < orders_count; i++) {
  451. orders[i].id = i;
  452. fs >> orders[i].x >> orders[i].y;
  453.  
  454. i64 cnt;
  455. fs >> cnt;
  456. for (i64 j = 0; j < cnt; j++) {
  457. i64 t;
  458. fs >> t;
  459. orders[i].items[t] += 1;
  460. }
  461. }
  462.  
  463. orders.resize(orders_count);
  464. for (i64 i = 0; i < orders_count; i++) {
  465. orders[i].wdist.resize(warehouses_count);
  466. for (i64 j = 0; j < warehouses_count; j++) {
  467. orders[i].wdist[j] = dist({orders[i].x, orders[i].y}, {warehouses[j].x, warehouses[j].y});
  468. }
  469. }
  470.  
  471. drones.resize(drones_count);
  472. for (i64 i = 0; i < drones_count; i++) {
  473. drones[i].id = i;
  474. drones[i].x = warehouses[0].x;
  475. drones[i].y = warehouses[0].y;
  476.  
  477. }
  478.  
  479. fs.close();
  480. }
  481.  
  482. void read_answer(string fname) {
  483. fstream fs;
  484. fs.open(fname, fstream::in);
  485.  
  486. fs.close();
  487. }
  488.  
  489. i64 estimate() {
  490. i64 R = 0;
  491. return R;
  492. }
  493.  
  494. bool validate() {
  495. return true;
  496. }
  497.  
  498.  
  499. void simul(Drone& drone, Action& act) {
  500. if (act.t == 'W') {
  501. drone.tm += act.wait;
  502. return;
  503. }
  504.  
  505. pair<i64, i64> dst = {drone.x, drone.y};
  506.  
  507. if (act.t == 'U' || act.t == 'L') {
  508. Warehouse &w = warehouses[act.warehouse_id];
  509. dst = {w.x, w.y};
  510. }
  511.  
  512. if (act.t == 'D') {
  513. Order &o = orders[act.order_id];
  514. dst = {o.x, o.y};
  515. }
  516.  
  517. drone.tm += dist({drone.x, drone.y}, dst);
  518. drone.x = dst.first;
  519. drone.y = dst.second;
  520. }
  521.  
  522. void simul() {
  523. for (i64 i = 0; i < drones_count; i++) {
  524. Drone& drone = drones[i];
  525.  
  526. for (auto& act : drone.acts) {
  527. simul(drone, act);
  528. }
  529. }
  530. }
  531.  
  532. void calc_split(Order& o) {
  533. vector<i64> weights;
  534. for (auto t : o.items) {
  535. for (i64 i = 0; i < t.second; i++) {
  536. weights.push_back(t.first);
  537. }
  538. }
  539. sort(weights.begin(), weights.end(),
  540. [] (const auto& i, const auto& j) {
  541. return products[i].w < products[j].w;
  542. });
  543.  
  544. vector<map<i64, i64>>& R = o.split;
  545.  
  546. map<i64, i64> c;
  547. i64 cv;
  548. for (auto i : weights) {
  549. if (cv + products[i].w > max_load) {
  550. R.push_back(c);
  551. cv = 0;
  552. c = map<i64, i64>();
  553. }
  554.  
  555. cv += products[i].w;
  556. c[i] += 1;
  557. }
  558. R.push_back(c);
  559. }
  560.  
  561. i64 val(Order& o, Warehouse& w) {
  562. return o.wdist[w.id] * 2 * o.split.size();
  563. }
  564.  
  565. void simul(Drone& d, Warehouse& w, Order& o, map<i64, i64> q) {
  566. for (auto p : q) {
  567. Action a;
  568. a.t = 'L';
  569. a.drone_id = d.id;
  570. a.warehouse_id = w.id;
  571. a.product_id = p.first;
  572. a.cnt = p.second;
  573. actions.push_back(a);
  574. }
  575.  
  576.  
  577. for (auto p : q) {
  578. Action a;
  579. a.t = 'D';
  580. a.drone_id = d.id;
  581. a.order_id = o.id;
  582. a.product_id = p.first;
  583. a.cnt = p.second;
  584. actions.push_back(a);
  585. }
  586.  
  587. i64 tm = 0;
  588. tm += q.size() * 2;
  589. tm += o.wdist[w.id];
  590. d.tm += tm;
  591. }
  592.  
  593. i64 solve() {
  594. for (i64 i = 0; i < orders_count; i++) {
  595. calc_split(orders[i]);
  596. }
  597.  
  598. vector<pair<i64, i64>> vals;
  599. for (i64 i = 0; i < orders_count; i++) {
  600. Order& order = orders[i];
  601. Warehouse& warehouse = warehouses[0];
  602. vals.push_back({val(order, warehouse), order.id});
  603. }
  604.  
  605. sort(vals.begin(), vals.end());
  606.  
  607. for (auto v : vals) {
  608. auto& w = warehouses[0];
  609. auto& o = orders[v.second];
  610.  
  611. for (auto q : o.split) {
  612. i64 did = -1;
  613. for (i64 i = 0; i < drones_count; i++) {
  614. if (did < 0 || drones[i].tm < drones[did].tm) {
  615. did = i;
  616. }
  617. }
  618.  
  619. Drone& d = drones[did];
  620. simul(d, w, o, q);
  621. }
  622.  
  623. }
  624.  
  625. i64 R = 0;
  626. return R;
  627. }
  628.  
  629. void viz() {
  630. for (i64 i = 0; i < orders_count; i++) {
  631. Order& order = orders[i];
  632. i64 w = 0;
  633. for (auto it : order.items) {
  634. w += products[it.first].w * it.second;
  635. }
  636. cerr << w << endl;
  637. }
  638. }
  639.  
  640. void print_answer(string fname) {
  641. fstream fs;
  642. fs.open(fname, fstream::out);
  643.  
  644. fs << actions.size() << endl;
  645. for (auto a : actions) {
  646. stringstream ss;
  647. ss << a.drone_id << " " << a.t << " ";
  648. if (a.t == 'L') {
  649. ss << a.warehouse_id << " ";
  650. } else if (a.t == 'D') {
  651. ss << a.order_id << " ";
  652. }
  653. ss << a.product_id << " ";
  654. ss << a.cnt;
  655. fs << ss.str() << endl;
  656. }
  657. fs.close();
  658. }
  659.  
  660. int main(int argc, char* argv[]) {
  661. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);
  662. time_t start = time(0);
  663.  
  664. read_data(argv[2]);
  665.  
  666. const string mode = argv[1];
  667. if (mode == "solve") {
  668. i64 R = solve();
  669. cerr << R << endl;
  670. print_answer(argv[3]);
  671. } else if (mode == "check") {
  672. read_answer(argv[3]);
  673. }
  674.  
  675. bool ok = validate();
  676. i64 r = estimate();
  677.  
  678. cerr << "Ok: " << ok << endl;
  679. cerr << "Score: " << r << endl;
  680.  
  681. FILE *in = fopen(argv[2], "r");
  682. FILE *out = fopen(argv[3], "r");
  683.  
  684. cerr << ALL_THIS_SHIT::simulate(in, out) << endl;
  685. time_t stop = time(0);
  686. cerr << "Runtime: " << stop - start << endl;
  687. return 0;
  688. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement