Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <iostream>
- #include <iomanip>
- #include <sstream>
- #include <fstream>
- #include <stdint.h>
- #include <string.h>
- #define _USE_MATH_DEFINES
- #include <math.h>
- #include <vector>
- #include <list>
- #include <set>
- #include <map>
- #include <unordered_map>
- #include <unordered_set>
- #include <queue>
- #include <stack>
- #include <deque>
- #include <string>
- #include <algorithm>
- #include <functional>
- #include <bitset>
- #include <functional>
- #include <chrono>
- #include <random>
- #define sqr(x) (x) * (x)
- typedef unsigned int u32;
- typedef int i32;
- typedef unsigned long long int u64;
- typedef long long int i64;
- typedef uint16_t u16;
- typedef int16_t i16;
- typedef uint8_t u8;
- typedef int8_t i8;
- using namespace std;
- using namespace std::chrono;
- const i64 mod = 1000000007ll;
- const i64 smod = 998244353ll;
- const i64 inf = 10000000000000007ll;
- const double eps = 1e-10;
- const i64 MAXN = 10004;
- const i64 MAXM = 1000001;
- namespace ALL_THIS_SHIT {
- struct World {
- int height, width;
- int dronesCount;
- int maxTime;
- int maxWeight;
- int productsCount;
- int warehousesCount;
- int ordersCount;
- } world;
- struct Product {
- int weight;
- };
- vector<Product> products;
- struct Warehouse {
- int y, x;
- vector<int> productsCount;
- };
- vector<Warehouse> warehouses;
- struct Order {
- int y, x;
- vector<int> productsCount;
- };
- vector<Order> orders;
- struct Drone {
- int y, x;
- int time;
- int weight;
- vector<int> productsCount;
- void moveTo(int ty, int tx) {
- double dy = y - ty;
- double dx = x - tx;
- double d = ceil(hypot(dx, dy));
- y = ty;
- x = tx;
- time += d;
- }
- void moveToWarehouse(int i) {
- assert(0 <= i && i < world.warehousesCount);
- moveTo(warehouses[i].y, warehouses[i].x);
- }
- void moveToOrder(int i) {
- assert(0 <= i && i < world.ordersCount);
- moveTo(orders[i].y, orders[i].x);
- }
- void wait(int waitTime) {
- assert(0 < waitTime);
- time += waitTime;
- }
- };
- vector<Drone> drones;
- struct Event {
- enum { UNLOAD, LOAD, DELIVER } type;
- int time;
- int droneIndex;
- int recipientIndex;
- int productIndex;
- int productAmount;
- bool operator < (const Event &that) const {
- return tie(time, type) < tie(that.time, that.type);
- }
- int process() {
- assert(0 <= droneIndex && droneIndex < world.dronesCount);
- Drone &drone = drones[droneIndex];
- assert(0 <= productIndex && productIndex < world.productsCount);
- assert(0 < productAmount);
- drone.time = time;
- if (type == Event::UNLOAD) {
- assert(0 <= recipientIndex && recipientIndex < world.warehousesCount);
- assert(drone.productsCount[productIndex] >= productAmount);
- drone.time++;
- assert(drone.time < world.maxTime);
- drone.weight -= productAmount * products[productIndex].weight;
- drone.productsCount[productIndex] -= productAmount;
- warehouses[recipientIndex].productsCount[productIndex] += productAmount;
- return 0;
- }
- if (type == Event::LOAD) {
- assert(0 <= recipientIndex && recipientIndex < world.warehousesCount);
- assert(warehouses[recipientIndex].productsCount[productIndex] >= productAmount);
- drone.time++;
- assert(drone.time < world.maxTime);
- drone.weight += productAmount * products[productIndex].weight;
- assert(drone.weight <= world.maxWeight);
- drone.productsCount[productIndex] += productAmount;
- warehouses[recipientIndex].productsCount[productIndex] -= productAmount;
- return 0;
- }
- if (type == Event::DELIVER) {
- assert(0 <= recipientIndex && recipientIndex < world.ordersCount);
- assert(drone.productsCount[productIndex] >= productAmount);
- assert(orders[recipientIndex].productsCount[productIndex] >= productAmount);
- drone.time++;
- assert(drone.time < world.maxTime);
- drone.weight -= productAmount * products[productIndex].weight;
- drone.productsCount[productIndex] -= productAmount;
- orders[recipientIndex].productsCount[productIndex] -= productAmount;
- if (*max_element(orders[recipientIndex].productsCount.begin(), orders[recipientIndex].productsCount.end()) == 0) {
- long long completionTime = drone.time;
- double score = (world.maxTime - completionTime);
- score /= world.maxTime;
- score *= 100;
- return ceil(score);
- }
- return 0;
- }
- }
- };
- vector<Event> events;
- void readInput(FILE *f) {
- fscanf(f, "%d%d", &world.height, &world.width);
- fscanf(f, "%d", &world.dronesCount);
- fscanf(f, "%d", &world.maxTime);
- fscanf(f, "%d", &world.maxWeight);
- fscanf(f, "%d", &world.productsCount);
- products.resize(world.productsCount);
- for (int i = 0; i < world.productsCount; i++)
- fscanf(f, "%d", &products[i].weight);
- fscanf(f, "%d", &world.warehousesCount);
- warehouses.resize(world.warehousesCount);
- for (int i = 0; i < world.warehousesCount; i++) {
- fscanf(f, "%d%d", &warehouses[i].y, &warehouses[i].x);
- warehouses[i].productsCount.resize(world.productsCount);
- for (int j = 0; j < world.productsCount; j++)
- fscanf(f, "%d", &warehouses[i].productsCount[j]);
- }
- fscanf(f, "%d", &world.ordersCount);
- orders.resize(world.ordersCount);
- for (int i = 0; i < world.ordersCount; i++) {
- fscanf(f, "%d%d", &orders[i].y, &orders[i].x);
- orders[i].productsCount.resize(world.productsCount);
- int p;
- fscanf(f, "%d", &p);
- for (int j = 0; j < p; j++) {
- int x;
- fscanf(f, "%d", &x);
- orders[i].productsCount[x]++;
- }
- }
- }
- void initializeDrones() {
- drones.resize(world.dronesCount);
- for (auto &drone : drones) {
- drone.y = warehouses[0].y;
- drone.x = warehouses[0].x;
- drone.time = 0;
- drone.weight = 0;
- drone.productsCount.resize(world.productsCount);
- }
- }
- void readOutputAndMakeEvents(FILE *f) {
- int commandsCount;
- fscanf(f, "%d", &commandsCount);
- assert(0 <= commandsCount && commandsCount <= world.dronesCount * world.maxTime);
- initializeDrones();
- events.clear();
- for (int cmdI = 0; cmdI < commandsCount; cmdI++) {
- int droneIndex;
- char command;
- fscanf(f, "%d %c", &droneIndex, &command);
- assert(0 <= droneIndex && droneIndex < world.dronesCount);
- if (command == 'L' || command == 'U') {
- int warehouseIndex;
- fscanf(f, "%d", &warehouseIndex);
- assert(0 <= warehouseIndex && warehouseIndex < world.warehousesCount);
- int productIndex;
- fscanf(f, "%d", &productIndex);
- assert(0 <= productIndex && productIndex < world.productsCount);
- int productAmount;
- fscanf(f, "%d", &productAmount);
- assert(0 < productAmount);
- drones[droneIndex].moveToWarehouse(warehouseIndex);
- events.push_back({
- (command == 'L' ? Event::LOAD : Event::UNLOAD),
- drones[droneIndex].time,
- droneIndex,
- warehouseIndex,
- productIndex,
- productAmount
- });
- } else if (command == 'D') {
- int orderIndex;
- fscanf(f, "%d", &orderIndex);
- assert(0 <= orderIndex && orderIndex < world.ordersCount);
- int productIndex;
- fscanf(f, "%d", &productIndex);
- assert(0 <= productIndex && productIndex < world.productsCount);
- int productAmount;
- fscanf(f, "%d", &productAmount);
- assert(0 < productAmount);
- drones[droneIndex].moveToOrder(orderIndex);
- events.push_back({
- Event::DELIVER,
- drones[droneIndex].time,
- droneIndex,
- orderIndex,
- productIndex,
- productAmount
- });
- } else if (command == 'W') {
- int waitTime;
- fscanf(f, "%d", &waitTime);
- assert(0 < waitTime);
- drones[droneIndex].wait(waitTime);
- } else {
- assert(0);
- }
- }
- }
- int simulate(FILE *in, FILE *out) {
- readInput(in);
- readOutputAndMakeEvents(out);
- sort(events.begin(), events.end());
- int totalScore = 0;
- for (auto &e : events) {
- totalScore += e.process();
- }
- return totalScore;
- }
- }
- i64 dist(pair<i64, i64> p1, pair<i64, i64> p2) {
- return (i64)ceil(sqrt(sqr(p1.first - p2.first) + sqr(p1.second - p2.second)));
- }
- struct Product {
- i64 id;
- i64 w;
- };
- struct Warehouse {
- i64 id;
- i64 x;
- i64 y;
- map<i64, i64> items;
- };
- struct Order {
- i64 id;
- i64 x;
- i64 y;
- vector<i64> wdist;
- vector<map<i64, i64>> split;
- map<i64, i64> items;
- map<i64, i64> inflight;
- };
- struct Action {
- i64 drone_id;
- char t;
- i64 order_id;
- i64 warehouse_id;
- i64 product_id;
- i64 cnt;
- i64 wait;
- };
- struct DroneState {
- i64 tm;
- i64 x;
- i64 y;
- };
- struct Drone {
- i64 id;
- i64 x;
- i64 y;
- i64 tm;
- vector<Action> acts;
- vector<DroneState> states;
- };
- i64 rows, columns, drones_count, deadline, max_load;
- i64 products_count, warehouses_count, orders_count;
- vector<Product> products;
- vector<Warehouse> warehouses;
- vector<Order> orders;
- vector<Drone> drones;
- vector<Action> actions;
- void read_data(string fname) {
- fstream fs;
- fs.open(fname, fstream::in);
- fs >> rows >> columns >> drones_count >> deadline >> max_load;
- fs >> products_count;
- products.resize(products_count);
- for (i64 i = 0; i < products_count; i++) {
- products[i].id = i;
- fs >> products[i].w;
- }
- fs >> warehouses_count;
- warehouses.resize(warehouses_count);
- for (i64 i = 0; i < warehouses_count; i++) {
- warehouses[i].id = i;
- fs >> warehouses[i].x >> warehouses[i].y;
- for (i64 j = 0; j < products_count; j++) {
- i64 t;
- fs >> t;
- if (t > 0) {
- warehouses[i].items[j] = t;
- }
- }
- }
- fs >> orders_count;
- orders.resize(orders_count);
- for (i64 i = 0; i < orders_count; i++) {
- orders[i].id = i;
- fs >> orders[i].x >> orders[i].y;
- i64 cnt;
- fs >> cnt;
- for (i64 j = 0; j < cnt; j++) {
- i64 t;
- fs >> t;
- orders[i].items[t] += 1;
- }
- }
- orders.resize(orders_count);
- for (i64 i = 0; i < orders_count; i++) {
- orders[i].wdist.resize(warehouses_count);
- for (i64 j = 0; j < warehouses_count; j++) {
- orders[i].wdist[j] = dist({orders[i].x, orders[i].y}, {warehouses[j].x, warehouses[j].y});
- }
- }
- drones.resize(drones_count);
- for (i64 i = 0; i < drones_count; i++) {
- drones[i].id = i;
- drones[i].x = warehouses[0].x;
- drones[i].y = warehouses[0].y;
- }
- fs.close();
- }
- void read_answer(string fname) {
- fstream fs;
- fs.open(fname, fstream::in);
- fs.close();
- }
- i64 estimate() {
- i64 R = 0;
- return R;
- }
- bool validate() {
- return true;
- }
- void simul(Drone& drone, Action& act) {
- if (act.t == 'W') {
- drone.tm += act.wait;
- return;
- }
- pair<i64, i64> dst = {drone.x, drone.y};
- if (act.t == 'U' || act.t == 'L') {
- Warehouse &w = warehouses[act.warehouse_id];
- dst = {w.x, w.y};
- }
- if (act.t == 'D') {
- Order &o = orders[act.order_id];
- dst = {o.x, o.y};
- }
- drone.tm += dist({drone.x, drone.y}, dst);
- drone.x = dst.first;
- drone.y = dst.second;
- }
- void simul() {
- for (i64 i = 0; i < drones_count; i++) {
- Drone& drone = drones[i];
- for (auto& act : drone.acts) {
- simul(drone, act);
- }
- }
- }
- void calc_split(Order& o) {
- vector<i64> weights;
- for (auto t : o.items) {
- for (i64 i = 0; i < t.second; i++) {
- weights.push_back(t.first);
- }
- }
- sort(weights.begin(), weights.end(),
- [] (const auto& i, const auto& j) {
- return products[i].w < products[j].w;
- });
- vector<map<i64, i64>>& R = o.split;
- map<i64, i64> c;
- i64 cv;
- for (auto i : weights) {
- if (cv + products[i].w > max_load) {
- R.push_back(c);
- cv = 0;
- c = map<i64, i64>();
- }
- cv += products[i].w;
- c[i] += 1;
- }
- R.push_back(c);
- }
- i64 val(Order& o, Warehouse& w) {
- return o.wdist[w.id] * 2 * o.split.size();
- }
- void simul(Drone& d, Warehouse& w, Order& o, map<i64, i64> q) {
- for (auto p : q) {
- Action a;
- a.t = 'L';
- a.drone_id = d.id;
- a.warehouse_id = w.id;
- a.product_id = p.first;
- a.cnt = p.second;
- actions.push_back(a);
- }
- for (auto p : q) {
- Action a;
- a.t = 'D';
- a.drone_id = d.id;
- a.order_id = o.id;
- a.product_id = p.first;
- a.cnt = p.second;
- actions.push_back(a);
- }
- i64 tm = 0;
- tm += q.size() * 2;
- tm += o.wdist[w.id];
- d.tm += tm;
- }
- i64 solve() {
- for (i64 i = 0; i < orders_count; i++) {
- calc_split(orders[i]);
- }
- vector<pair<i64, i64>> vals;
- for (i64 i = 0; i < orders_count; i++) {
- Order& order = orders[i];
- Warehouse& warehouse = warehouses[0];
- vals.push_back({val(order, warehouse), order.id});
- }
- sort(vals.begin(), vals.end());
- for (auto v : vals) {
- auto& w = warehouses[0];
- auto& o = orders[v.second];
- for (auto q : o.split) {
- i64 did = -1;
- for (i64 i = 0; i < drones_count; i++) {
- if (did < 0 || drones[i].tm < drones[did].tm) {
- did = i;
- }
- }
- Drone& d = drones[did];
- simul(d, w, o, q);
- }
- }
- i64 R = 0;
- return R;
- }
- void viz() {
- for (i64 i = 0; i < orders_count; i++) {
- Order& order = orders[i];
- i64 w = 0;
- for (auto it : order.items) {
- w += products[it.first].w * it.second;
- }
- cerr << w << endl;
- }
- }
- void print_answer(string fname) {
- fstream fs;
- fs.open(fname, fstream::out);
- fs << actions.size() << endl;
- for (auto a : actions) {
- stringstream ss;
- ss << a.drone_id << " " << a.t << " ";
- if (a.t == 'L') {
- ss << a.warehouse_id << " ";
- } else if (a.t == 'D') {
- ss << a.order_id << " ";
- }
- ss << a.product_id << " ";
- ss << a.cnt;
- fs << ss.str() << endl;
- }
- fs.close();
- }
- int main(int argc, char* argv[]) {
- ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);
- time_t start = time(0);
- read_data(argv[2]);
- const string mode = argv[1];
- if (mode == "solve") {
- i64 R = solve();
- cerr << R << endl;
- print_answer(argv[3]);
- } else if (mode == "check") {
- read_answer(argv[3]);
- }
- bool ok = validate();
- i64 r = estimate();
- cerr << "Ok: " << ok << endl;
- cerr << "Score: " << r << endl;
- FILE *in = fopen(argv[2], "r");
- FILE *out = fopen(argv[3], "r");
- cerr << ALL_THIS_SHIT::simulate(in, out) << endl;
- time_t stop = time(0);
- cerr << "Runtime: " << stop - start << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement