SHARE
TWEET

VRt Contest Codeforces

a guest May 14th, 2019 189 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. struct location {
  8.     int x, y, d, p, l, h, num;
  9.     location(int _x = 0, int _y = 0, int _d = 0, int _p = 0, int _l = 0, int _h = 0, int _num = 0) {
  10.         x = _x, y = _y, d = _d, p = _p, l = _l, h = _h, num = _num;
  11.     }
  12. };
  13.  
  14. // list of all locations
  15. vector <location> loc;
  16. location base;
  17.  
  18. // magic choose
  19. bool choose = false;
  20.  
  21. // calculate dist between 2 locations
  22. int dist(const location & a, const location & b) {
  23.     return abs(a.x - b.x) + abs(a.y - b.y);
  24. }
  25.  
  26. // next best location
  27. int find_new_location(vector <location> & one, vector <bool> & done, location & prev, int time, int m, int len, int magic, int magic2, int magic3) {
  28.     int min_dist = 1e9, idx = -1;
  29.  
  30.     for (int i = 0; i < m; ++i) {
  31.         // time, when workers can start
  32.         int arrive_time = max(one[i].l, time + dist(prev, one[i]));
  33.  
  34.         // possible or not
  35.         if (done[i] || one[i].h < one[i].d + arrive_time) continue;
  36.  
  37.         // offset towards base
  38.         int delta = dist(one[i], base) - dist(prev, base);
  39.  
  40.         // calculate some magic ^_^
  41.         int tmp = delta * (len - magic2) - one[i].h * magic3 / 3;
  42.         if (choose) tmp = delta * (len - magic2) - (one[i].h - one[i].d / 15) * magic3 / 3;
  43.         tmp /= magic;
  44.  
  45.         // refresh best values
  46.         if (arrive_time - tmp < min_dist) {
  47.             min_dist = arrive_time - tmp;
  48.             idx = i;
  49.         }
  50.     }
  51.  
  52.     // number of next location
  53.     return idx;
  54. }
  55.  
  56. // main function
  57. int f(int mg, int mg2, int mg3, bool debug = true) {
  58.     // total sum
  59.     int sum = 0;
  60.  
  61.     // group of workers
  62.     for (int workers = 1; workers <= 7; ++workers) {
  63.         // answer
  64.         string answer_line;
  65.         vector <string> ans;
  66.  
  67.         // list of locations with loc[i].p == workers
  68.         vector <location> one;
  69.         for (int i = 0; i < (int) loc.size(); ++i) {
  70.             if (loc[i].p == workers) one.push_back(loc[i]);
  71.         }
  72.  
  73.         // all, left, completed localions
  74.         int m = one.size();
  75.         int left = m;
  76.         vector <bool> done(m, false);
  77.  
  78.         while (left > 0) {
  79.             location prev = base;
  80.  
  81.             // find start_time
  82.             int idx = find_new_location(one, done, prev, 0, m, 0, mg, mg2, mg3);
  83.             int start_time = 0;
  84.  
  85.             // check
  86.             if (idx != -1) start_time = one[idx].l - dist(base, one[idx]);
  87.             else break;
  88.  
  89.             // current time
  90.             int time = start_time;
  91.  
  92.             // sum and asnwer per one pass
  93.             int local_sum = 0;
  94.             vector <string> local_ans;
  95.  
  96.             // answer
  97.             if (!debug) {
  98.                 answer_line = "start " + to_string(time) + " 1";
  99.                 local_ans.push_back(answer_line);
  100.             }
  101.  
  102.             // length of paths
  103.             int len = 0;
  104.             while (true) {
  105.                 // find new location
  106.                 int idx = find_new_location(one, done, prev, time, m, len, mg, mg2, mg3);
  107.                 if (idx == -1) break;
  108.  
  109.                 done[idx] = true;
  110.                 left--;
  111.                 location job = one[idx];
  112.  
  113.                 // working
  114.                 int arrive_time = max(job.l, time + dist(prev, job));
  115.  
  116.                 // answer
  117.                 if (!debug) {
  118.                     answer_line = "arrive " + to_string(arrive_time) + " " + to_string(job.num);
  119.                     local_ans.push_back(answer_line);
  120.                     answer_line = "work " + to_string(arrive_time) + " " + to_string(arrive_time + job.d) + " " + to_string(job.num);
  121.                     local_ans.push_back(answer_line);
  122.                 }
  123.  
  124.                 // profit
  125.                 local_sum += job.d * job.p * (job.p + 5);
  126.  
  127.                 // update
  128.                 prev = job;
  129.                 time = job.d + arrive_time;
  130.                 len++;
  131.             }
  132.  
  133.             // answer
  134.             if (!debug) {
  135.                 answer_line = "arrive " + to_string(time + dist(prev, base)) + " 1";
  136.                 local_ans.push_back(answer_line);
  137.                 answer_line = "end";
  138.                 local_ans.push_back(answer_line);
  139.             }
  140.  
  141.             // lost
  142.             local_sum -= (time - start_time) * workers;
  143.             local_sum -= dist(prev, base) * workers;
  144.             local_sum -= 240 * workers;
  145.  
  146.             // Only (profit > lost) deals
  147.             if (local_sum > 0) {
  148.                 sum += local_sum;
  149.  
  150.                 // print answer
  151.                 if (!debug) {
  152.                     for (int k = 0; k < workers; ++k) {
  153.                         for (auto e : local_ans) {
  154.                             cout << e << "\n";
  155.                         }
  156.                     }
  157.                 }
  158.             }
  159.         }
  160.     }
  161.  
  162.     return sum;
  163. }
  164.  
  165. int main() {
  166.     ios::sync_with_stdio(0);
  167.     int n;
  168.     cin >> n;
  169.  
  170.     int nil;
  171.     cin >> base.x >> base.y >> nil >> nil >> nil >> nil;
  172.  
  173.     // locations
  174.     loc.resize(n - 1);
  175.     for (int i = 0; i < n - 1; ++i) {
  176.         cin >> loc[i].x >> loc[i].y >> loc[i].d >> loc[i].p >> loc[i].l >> loc[i].h;
  177.         loc[i].num = i + 2;
  178.     }
  179.  
  180.     // calculate magic values
  181.     int magic = -1, magic2 = -1, magic3 = -1, max_magic = 0;
  182.     bool choose_val = false;
  183.     for (int mg2= -44; mg2 <= -23; ++mg2) {
  184.         for (int mg = 55; mg <= 83; ++mg) {
  185.             for (int mg3 = 9; mg3 <= 14; ++mg3) {
  186.                 int total = f(mg, mg2, mg3);
  187.  
  188.                 // for "magic choose"
  189.                 int total2 = 0;
  190.                 bool use_choose = false;
  191.                 if (n < 1000) {
  192.                     choose = true;
  193.                     total2 = f(mg, mg2, mg3);
  194.                     choose = false;
  195.                     if (total2 > total) {
  196.                         total = total2;
  197.                         use_choose = true;
  198.                     }
  199.                 }
  200.  
  201.                 if (total > max_magic) {
  202.                     max_magic = total;
  203.                     magic = mg;
  204.                     magic2 = mg2;
  205.                     magic3 = mg3;
  206.                     choose_val = use_choose;
  207.                 }
  208.             }
  209.         }
  210.     }
  211.     choose = choose_val;
  212.  
  213.     //cout << "total sum = " << max_magic << endl;
  214.     //cout << "choose_val = " << choose << endl;
  215.     //cout << "magic, magic2, magic3 = " << magic << ' ' << magic2 << ' ' << magic3 << endl;
  216.  
  217.     // Get answer
  218.     f(magic, magic2, magic3, false);
  219. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top