SHARE
TWEET

VRt Contest 2019 - T1024

a guest May 15th, 2019 57 in 2 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <vector>
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <random>
  8. #ifdef _MSC_VER
  9. #   include <ctime>
  10. #else
  11. #   include <sys/time.h>
  12. #endif
  13.  
  14. #ifdef _LOCAL
  15. #   include <assert.h>
  16. #   include <dbg_print.h>
  17. #   define _NO_TIME
  18. #else
  19. #   define assert(ok) //{if(!(ok)) while(1);}
  20. #   define dprint(...)
  21. #   define FUNCTION_STAT
  22. #endif
  23.  
  24. using namespace std;
  25.  
  26. std::mt19937 g_rnd;
  27. std::uniform_real_distribution<double> g_dist(0.0, 1.0);
  28.  
  29. #define srand(s) g_rnd.seed(s)
  30.  
  31. #define rand g_rnd
  32.  
  33. double frand()
  34. {
  35.     return g_dist(g_rnd);
  36. }
  37.  
  38. int random(int low, int high)
  39. {
  40.     assert(0 <= high-low);
  41.     return low + rand()%(high-low+1);
  42. }
  43.  
  44.  
  45. class TimeLimit
  46. {
  47. public:
  48.     TimeLimit(double tl)
  49.         : t0(time())
  50.         , dt_limit(tl)
  51.     {}
  52.     double time() const
  53.     {
  54. #ifndef _MSC_VER
  55.         timeval tv;
  56.         gettimeofday(&tv,0);
  57.         return tv.tv_sec + 1e-6*tv.tv_usec;
  58. #else
  59.         return double(clock()) / CLOCKS_PER_SEC;
  60. #endif
  61.     }
  62.     void restart()
  63.     {
  64.         t0 = time();
  65.     }
  66.     double dt() const
  67.     {
  68.         return time() - t0;
  69.     }
  70.  
  71.     bool go() const
  72.     {
  73.         return dt()<dt_limit;
  74.     }
  75.  
  76.     double limit() const
  77.     {
  78.         return dt_limit;
  79.     }
  80.  
  81.     double left() const
  82.     {
  83.         return limit() - dt();
  84.     }
  85.  
  86. private:
  87.     double t0;
  88.     double dt_limit;
  89. };
  90.  
  91. struct OptManagerSA
  92. {
  93.     OptManagerSA(double q1, double q2, int step_limit, double time_limit)
  94.         : tl(time_limit)
  95.         , maxstep(step_limit)
  96.     {
  97.         step = 0;
  98.         q = q0 = q1;
  99. #ifdef _NO_TIME
  100.         dq = pow(q2/q0, 1.0/maxstep);
  101. #else
  102.         assert(0 < time_limit);
  103.         dq = q2/q0;
  104.         tc = tl.dt();
  105. #endif
  106.     }
  107.  
  108.     bool accept(double newscore)
  109.     {
  110.         /// Less is better!
  111.         if(newscore <= scurr+1E-9)
  112.             return true;
  113.         //return false;
  114.        
  115. #ifndef _NO_TIME
  116.         if((step&0xFF) == 0)
  117.         {
  118.             tc = tl.dt();
  119.             double t = tc / ( tl.limit());
  120.             q = q0*pow(dq, t);
  121.         }
  122. #endif
  123.         double x = (scurr-newscore)/q;
  124.         //if(x < -20.0)
  125.         //  return false;
  126.         double y;
  127.         if(-0.1 < x)
  128.             y = 1+x;
  129.         else
  130.             y = exp(x);
  131.         bool ok = (frand() < y);
  132.         return ok;
  133.     }
  134.  
  135.     void next_step(double newscore)
  136.     {
  137. #ifdef _NO_TIME
  138.         q *= dq;
  139. #endif
  140.         scurr = newscore;
  141.         ++step;
  142.     }
  143.  
  144.     bool go()
  145.     {
  146. #ifdef _NO_TIME
  147.         gogo = step < maxstep;
  148. #else
  149.         if((step&0xFF) == 0)
  150.             return gogo = tl.go();
  151. #endif
  152.         return gogo;
  153.     }
  154.  
  155.     double q0, q, dq;
  156.     int maxstep;
  157.     int step;
  158.     double scurr;
  159.  
  160.     double tc;
  161.     TimeLimit tl;
  162.     bool gogo = true;
  163. };
  164.  
  165.  
  166. struct Worker
  167. {
  168.     vector<int> locs;
  169.     int val;
  170.     bool special = false;
  171.     int base_p = -1;
  172. };
  173.  
  174. struct Job
  175. {
  176.     int x, y;
  177.     int d, p, orig_p;
  178.     int first, last;
  179.     bool done = false;
  180. };
  181.  
  182. int N;
  183. vector<Worker> workers;
  184. vector<Job> jobs;
  185. TimeLimit tl(14.0);
  186.  
  187. int dist(int loc1, int loc2)
  188. {
  189.     return std::abs(jobs[loc1].x - jobs[loc2].x) + std::abs(jobs[loc1].y - jobs[loc2].y);
  190. }
  191.  
  192.  
  193. const vector<int> &get_valid_inserts(const Worker &worker, const int locx)
  194. {
  195.     static vector<int> valid_pos;
  196.     valid_pos.clear();
  197.     if(worker.special)
  198.     {
  199.         valid_pos.push_back(worker.locs.size()-1);
  200.         return valid_pos;
  201.     }
  202.    
  203.     static int last_start[2048];
  204.     last_start[worker.locs.size()-1] = jobs[0].last;
  205.     static int first_start[2048] = {0};
  206.    
  207.     for(int pos = worker.locs.size()-2; 1<=pos; --pos)
  208.     {
  209.         int loc2 = worker.locs[pos+1];
  210.         int loc1 = worker.locs[pos];
  211.         last_start[pos] = min(jobs[loc1].last, last_start[pos+1] - jobs[loc1].d - dist(loc1, loc2));
  212.         assert(last_start[pos] >= jobs[loc1].first);
  213.     }
  214.  
  215.     for(int pos=0; pos+1<worker.locs.size(); ++pos)
  216.     {
  217.         int loc2 = worker.locs[pos+1];
  218.         int loc1 = worker.locs[pos];
  219.  
  220.         int t1 = first_start[pos] + jobs[loc1].d + dist(loc1, locx);
  221.         if(t1 > jobs[locx].last)
  222.             break;
  223.         int start2_new = max(t1, jobs[locx].first) + jobs[locx].d + dist(locx, loc2);
  224.         if(start2_new <= last_start[pos+1])// && t1 <= jobs[locx].last)
  225.             valid_pos.push_back(pos+1);
  226.  
  227.         first_start[pos+1] = max(jobs[loc2].first, first_start[pos] + jobs[loc1].d + dist(loc1, loc2));
  228.     }
  229.    
  230.     return valid_pos;
  231. }
  232.  
  233. int evaluate_single(Worker &worker, int )
  234. {
  235.     FUNCTION_STAT
  236.     if(worker.special)
  237.         return worker.val = 0;
  238.    
  239.     int score_invalid = -1000111000;
  240.     static int last_start[2048];
  241.  
  242.     last_start[worker.locs.size()-1] = jobs[worker.locs[worker.locs.size()-1]].last;
  243.    
  244.     for(int pos = worker.locs.size()-2; 1<=pos; --pos)
  245.     {
  246.         int loc2 = worker.locs[pos+1];
  247.         int loc1 = worker.locs[pos];
  248.         last_start[pos] = min(jobs[loc1].last, last_start[pos+1] - jobs[loc1].d - dist(loc1, loc2));
  249.         if(last_start[pos] < jobs[loc1].first)
  250.             return score_invalid;
  251.     }
  252.  
  253.     //int total_job_time = 0;
  254.     int total_free_time = 0;
  255.     int t = last_start[1];
  256.     int score = 0;
  257.     for(int pos=1; pos+1<worker.locs.size(); ++pos)
  258.     {
  259.         int loc1 = worker.locs[pos];
  260.         int loc2 = worker.locs[pos+1];
  261.         t += jobs[loc1].d + dist(loc1, loc2);
  262.         total_free_time += max(0, jobs[loc2].first - t);
  263.         t = max(t, jobs[loc2].first);
  264.         //if(last_start[pos+1] < t) {
  265.             //assert(0);
  266.             //return score_invalid;
  267.         //}
  268.         //total_job_time += jobs[loc1].d;
  269.         score += jobs[loc1].d * (jobs[loc1].p + 5);
  270.     }
  271.    
  272.     int duration = t - last_start[1] + dist(0,worker.locs[1]);
  273.     score -= 240 + duration;
  274.     //dprint(score, p, total_job_time, duration);
  275.     int value = score + total_free_time/2;//1000*score + total_free_time;
  276.    
  277.     int np[8] = {0};
  278.     for(int loc : worker.locs)
  279.         ++np[jobs[loc].orig_p];
  280.     int maxp = 0;
  281.     for(int p=1; p<=7; ++p) if(np[p])
  282.         maxp = p;
  283.     if(maxp < worker.base_p) {
  284.         value += 240/worker.base_p;
  285.     }
  286.    
  287.     value = max(0, value);
  288.     worker.val = value;
  289.     return value;
  290. }
  291.  
  292. int evaluate_sum()
  293. {
  294.     int res = 0;
  295.     for(Worker &w : workers)
  296.         res += evaluate_single(w,-1)*jobs[w.locs[1]].p;
  297.     return res;
  298. }
  299.  
  300. int get_valid_rand_pos(const Worker &worker, int locx)
  301. {
  302.     FUNCTION_STAT
  303.     const vector<int> &valid_pos = get_valid_inserts(worker, locx);
  304.     if(valid_pos.empty())
  305.         return -1;
  306.     int idx = valid_pos[rand()%valid_pos.size()];
  307.     return idx;
  308. }
  309.  
  310. void optimize(Worker &worker, int p)
  311. {
  312.     int value = evaluate_single(worker, p);
  313.    
  314.     for(int step=0; step<99999; ++step)
  315.     {
  316.         assert(worker.locs.front() == 0 && worker.locs.back() == 0);
  317.         int r = 0;//rand()%2;
  318.         if(r == 0)// && 4 <= worker.locs.size())
  319.         {
  320.             int ijob = 1 + rand()%(N-1);
  321.             if(jobs[ijob].done || jobs[ijob].p != p)
  322.                 continue;
  323.            
  324.             int idx = get_valid_rand_pos(worker, ijob);
  325.             if(idx < 0)
  326.                 continue;
  327.            
  328.             Worker backup = worker;
  329.             worker.locs.insert(worker.locs.begin() + idx, ijob);
  330.             int v = evaluate_single(worker, p);
  331.             assert(-999 <= v);
  332.            
  333.             if(v < value)
  334.             {
  335.                 worker = backup;
  336.             }
  337.             else
  338.             {
  339.                 jobs[ijob].done = true;
  340.                 value = v;
  341.             }
  342.         }
  343.     }
  344.     assert(value == evaluate_single(worker, p));
  345. }
  346.  
  347. bool g_last_wave = false;
  348.  
  349. int evaluate_double(Worker &w1, Worker &w2, int p, bool recalc=true)
  350. {
  351.     int value;
  352.     if(!recalc)
  353.     {
  354.         value = w1.val;
  355.         if(&w1 != &w2)
  356.             value += w2.val;
  357.     }
  358.     else
  359.     {
  360.         value = evaluate_single(w1, p);
  361.         if(value < 0)
  362.             return value;
  363.         if(&w1 != &w2)
  364.             value += evaluate_single(w2, p);
  365.     }
  366.     if(!g_last_wave)
  367.         value += 1000 - 4*min(w1.locs.size(),w2.locs.size());
  368.     return value;
  369. }
  370.  
  371. void optimize(int maxstep, double time_limit, double q0)
  372. {
  373.     FUNCTION_STAT
  374.    
  375.     if(workers.size() < 2)
  376.         return;
  377.    
  378.     Worker backup1, backup2;
  379.     int currv=0;
  380.     for(auto &w : workers)
  381.         currv += evaluate_single(w, -1);
  382.    
  383.     OptManagerSA sa(q0, 0.1, maxstep, time_limit);
  384.     for(int step=0; sa.go(); ++step)
  385.     {
  386.         int r = rand()%25/10;
  387.         if(r == 0)
  388.         {
  389.             int iw1 = rand()%workers.size();
  390.             int iw2 = rand()%workers.size();
  391.            
  392.             Worker &w1 = workers[iw1];
  393.             Worker &w2 = workers[iw2];
  394.             if(w1.locs.size() <= 2)
  395.                 continue;
  396.             assert(jobs[w1.locs[1]].p == jobs[w2.locs[1]].p || w2.special);
  397.             assert((1 <= w2.base_p && w2.base_p <= 7) || w2.special);
  398.  
  399.             int p = jobs[w1.locs[1]].p;
  400.             int value = evaluate_double(w1, w2, p, false);
  401.             sa.next_step(-value);
  402.            
  403.             assert(2 < w1.locs.size());
  404.             int idx1 = 1 + rand() % (w1.locs.size()-2);
  405.            
  406.             backup1 = w1;
  407.             int loc1 = w1.locs[idx1];
  408.             w1.locs.erase(w1.locs.begin() + idx1);
  409.             int idx2 = get_valid_rand_pos(w2, loc1);
  410.             if(idx2 < 0) {
  411.                 w1 = backup1;
  412.                 continue;
  413.             }
  414.             backup2 = w2;
  415.             w2.locs.insert(w2.locs.begin() + idx2, loc1);
  416.             int v = evaluate_double(w1, w2, p);
  417.             assert(0 <= v);
  418.            
  419.             //if(v < value)
  420.             if(!sa.accept(-v))
  421.             {
  422.                 w2 = backup2;
  423.                 w1 = backup1;
  424.             }
  425.             else
  426.             {
  427.                 currv += -value+v;
  428.                 if(w1.locs.size() == 2 && !w1.special) {
  429.                     workers.erase(workers.begin() + iw1);
  430.                     currv += 240;
  431.                 }
  432.             }
  433.         }
  434.         else if(r == 1)
  435.         {
  436.             int iw1 = rand()%workers.size();
  437.             int iw2 = rand()%workers.size();
  438.             if(iw1 == iw2 || jobs[workers[iw1].locs[1]].p != jobs[workers[iw2].locs[1]].p)
  439.                 continue;
  440.            
  441.             Worker &w1 = workers[iw1];
  442.             Worker &w2 = workers[iw2];
  443.             int p = jobs[w1.locs[1]].p;
  444.             int value = evaluate_double(w1, w2, p, false);
  445.             sa.next_step(-value);
  446.            
  447.             backup1 = w1;
  448.             backup2 = w2;
  449.  
  450.             int idx1 = 1 + rand() % (w1.locs.size()-2);
  451.             //int idx2 = 1 + rand() % (w2.locs.size()-2);
  452.             int max_idx2 = w2.locs.size()-1;
  453.             for(int idx2=2; idx2+1<w2.locs.size(); ++idx2)
  454.             {
  455.                 int mint = jobs[w2.locs[idx2-1]].first + jobs[w2.locs[idx2-1]].d + dist(w2.locs[idx2-1], w1.locs[idx1]);
  456.                 if(mint > jobs[w1.locs[idx1]].last)
  457.                 {
  458.                     max_idx2 = idx2-1;
  459.                     break;
  460.                 }
  461.             }
  462.             //int idx2 = min_idx2 + rand() % (w2.locs.size()-min_idx2-1);
  463.             int idx2 = 1 + rand() % (max_idx2);
  464.            
  465.             vector<int> tmp1(w1.locs.begin()+idx1, w1.locs.end());
  466.             vector<int> tmp2(w2.locs.begin()+idx2, w2.locs.end());
  467.             w1.locs.erase(w1.locs.begin() + idx1, w1.locs.end());
  468.             w2.locs.erase(w2.locs.begin() + idx2, w2.locs.end());
  469.             w1.locs.insert(w1.locs.end(), tmp2.begin(), tmp2.end());
  470.             w2.locs.insert(w2.locs.end(), tmp1.begin(), tmp1.end());
  471.             int v = evaluate_double(w1, w2, p);
  472.  
  473.             //if(v < value)
  474.             if(!sa.accept(-v))
  475.             {
  476.                 w1 = backup1;
  477.                 w2 = backup2;
  478.             }
  479.             else
  480.             {
  481.                 currv += -value+v;
  482.                 if(w1.locs.size() == 2 && !w1.special) {
  483.                     workers.erase(workers.begin() + iw1);
  484.                     currv += 240;
  485.                 }
  486.                 if(w2.locs.size() == 2 && !w2.special) {
  487.                     workers.erase(workers.begin() + iw2);
  488.                     currv += 240;
  489.                 }
  490.             }
  491.            
  492.         }
  493.         else if(r == 2)
  494.         {
  495.             int iw1 = rand()%workers.size();
  496.             int iw2 = rand()%workers.size();
  497.             Worker &w1 = workers[iw1];
  498.             Worker &w2 = workers[iw2];
  499.  
  500.             if(iw1 == iw2 || w1.locs.size() <= 2 || w2.locs.size() <= 2)
  501.                 continue;
  502.             assert(jobs[w1.locs[1]].p == jobs[w2.locs[1]].p);
  503.            
  504.             int p = jobs[w1.locs[1]].p;
  505.             int value = evaluate_double(w1, w2, p, false);
  506.             sa.next_step(-value);
  507.            
  508.             assert(2 < w1.locs.size());
  509.             int idx1 = 1 + rand() % (w1.locs.size()-2);
  510.             int idx2 = 1 + rand() % (w2.locs.size()-2);
  511.            
  512.             backup1 = w1;
  513.             backup2 = w2;
  514.             int loc1 = w1.locs[idx1];
  515.             w1.locs.erase(w1.locs.begin() + idx1);
  516.             int loc2 = w2.locs[idx2];
  517.             w2.locs.erase(w2.locs.begin() + idx2);
  518.             int idx2b = get_valid_rand_pos(w2, loc1);
  519.             int idx1b = get_valid_rand_pos(w1, loc2);
  520.             if(idx2b < 0 || idx1b < 0) {
  521.                 w1 = backup1;
  522.                 w2 = backup2;
  523.                 continue;
  524.             }
  525.             w2.locs.insert(w2.locs.begin() + idx2b, loc1);
  526.             w1.locs.insert(w1.locs.begin() + idx1b, loc2);
  527.             int v = evaluate_double(w1, w2, p);
  528.             assert(0 <= v);
  529.            
  530.             //if(v < value)
  531.             if(!sa.accept(-v))
  532.             {
  533.                 w1 = backup1;
  534.                 w2 = backup2;
  535.             }
  536.             else
  537.             {
  538.                 currv += -value+v;
  539.                 if(w1.locs.size() == 2 && !w1.special) {
  540.                     workers.erase(workers.begin() + iw1);
  541.                     currv += 240;
  542.                 }
  543.             }
  544.         }
  545.     }
  546.     dprint(sa.step);
  547. }
  548.  
  549. int greedy(int p1=1, int p2=7, int maxw=9999)
  550. {
  551.     int total_score = 0;
  552.     //workers.clear();
  553.    
  554.     for(int p=p2; p1<=p && workers.size()<maxw; )
  555.     {
  556.         workers.push_back(Worker());
  557.         workers.back().locs.push_back(0);
  558.         workers.back().base_p = p;
  559.  
  560.         int loc = 0;
  561.         int t = 0;
  562.         int min_duration = 0, total_job_time = 0;
  563.         int total_dist = 0;
  564.        
  565.         while(1)
  566.         {
  567.             int next_loc = -1;
  568.             int best_val = 9999;
  569.             for(int i=1; i<N; ++i) if(jobs[i].p == p && !jobs[i].done)
  570.             {
  571.                 int t1 = max(t + dist(loc, i), jobs[i].first);
  572.                 if(t1 <= jobs[i].last)
  573.                 {
  574.                     int val = dist(loc,i)*10 + t1*4 + jobs[i].last*2;// + rand()%10;
  575.                     if(next_loc < 0 || val < best_val)
  576.                     {
  577.                         best_val = val;
  578.                         next_loc = i;
  579.                     }
  580.                 }
  581.             }
  582.  
  583.             if(next_loc < 0)
  584.                 break;
  585.            
  586.             workers.back().locs.push_back(next_loc);
  587.            
  588.             t = max(t + dist(loc, next_loc), jobs[next_loc].first) + jobs[next_loc].d;
  589.             min_duration += dist(loc, next_loc) + jobs[next_loc].d;
  590.             total_job_time += jobs[next_loc].d;
  591.             total_dist += dist(loc, next_loc);
  592.             loc = next_loc;
  593.             jobs[loc].done = true;
  594.         }
  595.        
  596.         workers.back().locs.push_back(0);      
  597.         optimize(workers.back(), p);
  598.        
  599.         if(workers.back().locs.size() <= 2)
  600.         {
  601.             workers.pop_back();
  602.             --p;
  603.            
  604.             continue;
  605.         }
  606.        
  607.         total_score += p*evaluate_single(workers.back(), p);
  608.     }
  609.  
  610.     return total_score;
  611. }
  612.  
  613.  
  614. void post(int q, bool finish=true)
  615. {
  616.     vector<bool> done(N, false);
  617.     vector<Worker> workersp[8];
  618.  
  619.     for(const Worker &w : workers)
  620.     {
  621.         int p = jobs[w.locs[1]].p;
  622.         workersp[p].push_back(w);
  623.         for(int loc : w.locs)
  624.             done[loc] = true;
  625.     }
  626.     workers.clear();
  627.  
  628.     for(int p=1; p<=7; ++p) {
  629.         workersp[p].push_back(Worker());
  630.         workersp[p].back().special = true;
  631.         workersp[p].back().locs.push_back(0);
  632.         workersp[p].back().locs.push_back(0);
  633.     }
  634.  
  635.     int sumstep = (2*9999*10*6 + 2*3111*10*6)/3;
  636.     double sumt = 12.0/q;
  637.     for(int p=2; p<=7 && tl.go(); ++p)
  638.     {
  639.         for(int i=0; i<q && tl.go(); ++i)
  640.         {
  641.             g_last_wave = (i>=q-1);
  642.             workers = workersp[p];
  643.             int step = sumstep*73/100;
  644.             double time_limit = sumt*73/100;
  645.             if(p <= 1) {
  646.                 step = sumstep*1/100;
  647.                 time_limit = sumt*1/100;
  648.             } else if(p <= 3) {
  649.                 step = sumstep*26/100;
  650.                 time_limit = sumt*26/100;
  651.             }
  652.             optimize(step, time_limit, 12.0 - i*5.0/q);
  653.             workersp[p]= workers;
  654.         }
  655.     }
  656.  
  657.     for(int p=1; p<=7; ++p) {
  658.         assert(workersp[p].back().special);
  659.         workersp[p].pop_back();
  660.     }
  661.  
  662.     workers.clear();
  663.     int total_score = 0;
  664.     for(int p=1; p<=7; ++p)
  665.     {
  666.         for(auto &w1 : workersp[p])
  667.         {
  668.             int s = evaluate_single(w1, p)*p;
  669.             if(s <= 0 && finish)
  670.             {
  671.                 for(int loc : w1.locs)
  672.                     done[loc] = false;
  673.             }
  674.             else
  675.             {
  676.                 for(int i=0; i<(finish?p:1); ++i)
  677.                     workers.push_back(w1);
  678.             }
  679.             total_score += s;
  680.         }
  681.     }
  682. }
  683.  
  684.  
  685. //======================================================================
  686.  
  687. struct W
  688. {
  689.     W() {}
  690.     W(int loc, int iw)
  691.         : loc(loc)
  692.         , iw(iw)
  693.     {}
  694.    
  695.     int loc;
  696.     int iw;
  697. };
  698.  
  699. struct Brigade
  700. {
  701.     vector<W> shift;
  702.     int size;
  703.     bool special = false;
  704. };
  705.  
  706. int write_sol2(const Brigade &br)
  707. {
  708.     static int last_start[2048];
  709.     static int start_time[2048];
  710.     int next_pos[7] = {0};
  711.     int prev_pos[7] = {0};
  712.  
  713.     int size = 0;
  714.     int score = 0;
  715.     for(const auto &w : br.shift)
  716.     {
  717.         last_start[w.loc] = 99999;
  718.         start_time[w.loc] = jobs[w.loc].first;
  719.         //score += jobs[w.loc].d * (jobs[w.loc].p + 5) * jobs[w.loc].p;
  720.         size = max(size, w.iw + jobs[w.loc].p);
  721.     }
  722.    
  723.     for(int pos = br.shift.size()-2; 1<=pos; --pos)
  724.     {
  725.         auto &w = br.shift[pos];
  726.         {
  727.             int loc1 = w.loc;
  728.             int iw = w.iw;
  729.             for(int i=0; i<jobs[w.loc].p; ++i)
  730.             {
  731.                 int loc2 = next_pos[iw];
  732.                 last_start[loc1] = min(last_start[loc1], min(jobs[loc1].last, last_start[loc2] - jobs[loc1].d - dist(loc1, loc2)));
  733.                 assert(last_start[loc1] >= jobs[loc1].first);
  734.                 next_pos[iw] = loc1;
  735.                 ++iw;
  736.             }
  737.             assert(iw <= size);
  738.         }
  739.     }
  740.    
  741.     for(int iw=0; iw<size; ++iw)
  742.     {
  743.         start_time[next_pos[iw]] = last_start[next_pos[iw]];
  744.     }
  745.  
  746.     int total_free_time = 0;
  747.     //int t = last_start[1];
  748.     for(int pos=1; pos+1<br.shift.size(); ++pos)
  749.     {
  750.         auto &w = br.shift[pos];
  751.         {
  752.             int loc2 = w.loc;
  753.             int iw = w.iw;
  754.             for(int i=0; i<jobs[loc2].p; ++i)
  755.             {
  756.                 int loc1 = prev_pos[iw];
  757.                 start_time[loc2] = max(start_time[loc2], start_time[loc1] + jobs[loc1].d + dist(loc1, loc2));
  758.                 //dprint(loc2, start_time[loc2]);
  759.                 assert(last_start[loc2] >= start_time[loc2]);
  760.                 prev_pos[iw] = loc2;
  761.                 ++iw;
  762.             }
  763.         }
  764.  
  765.         //total_free_time += max(0, jobs[loc2].first - t);
  766.     }
  767.  
  768.     vector<Worker> ww(br.size);
  769.    
  770.     for(auto &w : ww)
  771.         w.locs.push_back(0);
  772.    
  773.     for(const auto &w : br.shift)
  774.     {
  775.         for(int i=0; i<jobs[w.loc].p; ++i)
  776.             ww[i+w.iw].locs.push_back(w.loc);
  777.     }
  778.    
  779.     for(auto &w : ww)
  780.     {
  781.         w.locs.push_back(0);
  782.     }
  783.  
  784.     vector<int> nworker(N,0);
  785.    
  786.     for(Worker &w : ww)
  787.     {
  788.         int curr_pos = 0;
  789.         int curr_t = 0;
  790.         bool first = true;
  791.         int t0 = 0;
  792.         for(int j=1; j<w.locs.size(); ++j)
  793.         {
  794.             int loc = w.locs[j];
  795.             if(j+1 < w.locs.size())
  796.             {
  797.                 assert(start_time[loc] <= jobs[loc].last && jobs[loc].first <= start_time[loc]);
  798.                 assert(start_time[w.locs[j-1]] + jobs[w.locs[j-1]].d + dist(w.locs[j-1], loc) <= start_time[loc]);
  799.                
  800.                 if(nworker[loc] < jobs[loc].p)
  801.                 {
  802.                     ++nworker[loc];
  803.                     if(first) {
  804.                         first = false;
  805.                         t0 = (start_time[loc] - dist(0, loc));
  806.                         assert(0 <= t0 && t0 <= 1000);
  807.                         cout << "start " << " " << t0 << " " << 1 << "\n";
  808.                     }
  809.                     cout << "arrive  " << start_time[loc] << " " << loc+1 << "\n";
  810.                     cout << "work " << start_time[loc] << " " << start_time[loc] + jobs[loc].d << " " << loc+1 << "\n";
  811.                     curr_pos = loc;
  812.                     curr_t = start_time[loc] + jobs[loc].d;
  813.                     if(nworker[loc] == jobs[loc].p)
  814.                         score += jobs[loc].d * (jobs[loc].p + 5) * jobs[loc].p;
  815.                     assert(0 <= start_time[loc] && start_time[loc] + jobs[loc].d <= 1000);
  816.                     assert(1 <= loc+1 && loc+1 <= N);
  817.                 }
  818.             }
  819.             else if(!first)
  820.             {
  821.                 int loc1 = curr_pos;
  822.                 int t9 = curr_t + dist(loc1, 0);
  823.                 cout << "arrive  " << t9 << " " << 1 << "\n";
  824.                 assert(0 <= t9 && t9 <= 1000);
  825.                 assert(1 == loc+1);
  826.                 score -= 240 + (t9-t0);
  827.                 cout << "end\n";
  828.             }
  829.         }      
  830.     }
  831.    
  832.     return score;
  833. }
  834.  
  835. void write_sol2(const vector<Brigade> &br)
  836. {
  837.     int score = 0;
  838.     for(const auto &b : br)
  839.         score += write_sol2(b);
  840.     dprint(score);
  841. }
  842.  
  843.  
  844. int evaluate_brigade(const Brigade &br)
  845. {
  846.     FUNCTION_STAT
  847.     //if(worker.special)
  848.         //return worker.val = 0;
  849.    
  850.     int score_invalid = -1000111000;
  851.     static int last_start[2048];
  852.     static int start_time[2048];
  853.     int next_pos[7] = {0};
  854.     int prev_pos[7] = {0};
  855.  
  856.     int size = 0;
  857.     int score = 0;
  858.     for(const auto &w : br.shift)
  859.     {
  860.         last_start[w.loc] = 99999;
  861.         start_time[w.loc] = jobs[w.loc].first;
  862.         score += jobs[w.loc].d * (jobs[w.loc].p + 5) * jobs[w.loc].p;
  863.         size = max(size, w.iw + jobs[w.loc].p);
  864.     }
  865.    
  866.     for(int pos = br.shift.size()-2; 1<=pos; --pos)
  867.     {
  868.         auto &w = br.shift[pos];
  869.         {
  870.             int loc1 = w.loc;
  871.             int iw = w.iw;
  872.             for(int i=0; i<jobs[w.loc].p; ++i)
  873.             {
  874.                 int loc2 = next_pos[iw];
  875.                 last_start[loc1] = min(last_start[loc1], min(jobs[loc1].last, last_start[loc2] - jobs[loc1].d - dist(loc1, loc2)));
  876.                 if(last_start[loc1] < jobs[loc1].first)
  877.                     return score_invalid;
  878.                 next_pos[iw] = loc1;
  879.                 ++iw;
  880.             }
  881.             assert(iw <= size);
  882.         }
  883.     }
  884.    
  885.     for(int iw=0; iw<size; ++iw)
  886.     {
  887.         start_time[next_pos[iw]] = last_start[next_pos[iw]];
  888.     }
  889.  
  890.     int total_free_time = 0;
  891.     //int t = last_start[1];
  892.     for(int pos=1; pos+1<br.shift.size(); ++pos)
  893.     {
  894.         auto &w = br.shift[pos];
  895.         {
  896.             int loc2 = w.loc;
  897.             int iw = w.iw;
  898.             for(int i=0; i<jobs[loc2].p; ++i)
  899.             {
  900.                 int loc1 = prev_pos[iw];
  901.                 int t = start_time[loc1] + jobs[loc1].d + dist(loc1, loc2);
  902.                 start_time[loc2] = max(start_time[loc2], t);
  903.                 total_free_time += max(0, jobs[loc2].first - t);
  904.                 if(last_start[loc2] < start_time[loc2]) {
  905.                     return score_invalid-1;
  906.                 }
  907.                 prev_pos[iw] = loc2;
  908.                 ++iw;
  909.             }
  910.         }
  911.  
  912.         //total_free_time += max(0, jobs[loc2].first - t);
  913.     }
  914.  
  915.     for(int iw=0; iw<size; ++iw)
  916.     {
  917.         int duration = start_time[prev_pos[iw]] - last_start[next_pos[iw]] + jobs[prev_pos[iw]].d;
  918.         duration += dist(0, prev_pos[iw]) + dist(0, next_pos[iw]);
  919.         //dprint(iw, last_start[next_pos[iw]]-dist(0, next_pos[iw]), start_time[prev_pos[iw]], duration, next_pos[iw]);
  920.         score -= 240 + duration;
  921.     }
  922.     //score += total_free_time/4;
  923.     int value = max(0, score);
  924.     return value;
  925. }
  926.  
  927. const vector<int> &get_valid_inserts(const Brigade &br, const int locx, const int iw0)
  928. {
  929.     FUNCTION_STAT
  930.     static vector<int> valid_pos;
  931.     valid_pos.clear();
  932.     if(br.special)
  933.     {
  934.         valid_pos.push_back(br.shift.size()-1);
  935.         return valid_pos;
  936.     }
  937.    
  938.     static int first_start[2048];
  939.     static int last_start[2048];
  940.     int next_pos[7] = {0};
  941.     int prev_pos[7] = {0};
  942.  
  943.     int size = 0;
  944.     for(const auto &w : br.shift)
  945.     {
  946.         int loc = w.loc;
  947.         last_start[loc] = 99999;
  948.         first_start[loc] = jobs[loc].first;
  949.         size = max(size, w.iw + jobs[loc].p);
  950.     }
  951.    
  952.     for(int pos = br.shift.size()-2; 1<=pos; --pos)
  953.     {
  954.         auto &w = br.shift[pos];
  955.         {
  956.             int loc1 = w.loc;
  957.             int iw = w.iw;
  958.             for(int i=0; i<jobs[w.loc].p; ++i)
  959.             {
  960.                 int loc2 = next_pos[iw];
  961.                 last_start[loc1] = min(last_start[loc1], min(jobs[loc1].last, last_start[loc2] - jobs[loc1].d - dist(loc1, loc2)));
  962.                 assert(last_start[loc1] >= jobs[loc1].first);
  963.                 next_pos[iw] = loc1;
  964.                 ++iw;
  965.             }
  966.             assert(iw <= size);
  967.         }
  968.     }
  969.  
  970.     for(int pos=1; pos+1<=br.shift.size(); ++pos)
  971.     {
  972.         auto &w = br.shift[pos];
  973.         {
  974.             int loc2 = w.loc;
  975.             int iw = w.iw;
  976.             for(int i=0; i<jobs[loc2].p; ++i)
  977.             {
  978.                 int loc1 = prev_pos[iw];
  979.                 first_start[loc2] = max(first_start[loc2], first_start[loc1] + jobs[loc1].d + dist(loc1, loc2));
  980.                 assert(first_start[loc1] >= jobs[loc1].first);
  981.                 prev_pos[iw] = loc2;
  982.                 ++iw;
  983.             }
  984.             assert(iw <= size);
  985.         }
  986.     }
  987.    
  988.     static vector<int> wpos[7];
  989.     for(int pos=0; pos<br.shift.size(); ++pos)
  990.     {
  991.         if(pos == 0 || pos+1 == br.shift.size())
  992.         {
  993.             for(int iw=0; iw<br.size; ++iw) {
  994.                 if(pos == 0)
  995.                     wpos[iw].clear();
  996.                 wpos[iw].push_back(0);
  997.             }
  998.             continue;
  999.         }
  1000.        
  1001.         auto &w = br.shift[pos];
  1002.         {
  1003.             int loc = w.loc;
  1004.             int iw = w.iw;
  1005.             for(int i=0; i<jobs[loc].p; ++i)
  1006.             {
  1007.                 wpos[iw].push_back(loc);
  1008.                 ++iw;
  1009.             }
  1010.         }
  1011.     }
  1012.    
  1013.     static int start_2[2048];
  1014.    
  1015.     int pos_idx[7] = {0};
  1016.     for(int pos=1; pos+1<br.shift.size(); ++pos)
  1017.     {
  1018.         //auto &shift = br.shift[pos];
  1019.         int sump = iw0;
  1020.  
  1021.         {
  1022.             bool ok = true;
  1023.             int start_x = 0;
  1024.            
  1025.             for(int iw=sump; iw<sump+jobs[locx].p && ok; ++iw)
  1026.             {
  1027.                 assert(pos_idx[iw]+1 < wpos[iw].size());
  1028.                 int loc1 = wpos[iw][pos_idx[iw]];
  1029.                 int loc2 = wpos[iw][pos_idx[iw]+1];
  1030.                 start_2[loc2] = 0;
  1031.                 start_x = max(start_x, first_start[loc1] + jobs[loc1].d + dist(loc1, locx));
  1032.                 ok &= (start_x <= jobs[locx].last);
  1033.             }
  1034.  
  1035.             for(int iw=sump; iw<sump+jobs[locx].p && ok; ++iw)
  1036.             {
  1037.                 int loc2 = wpos[iw][pos_idx[iw]+1];
  1038.                 start_2[loc2] = max(start_2[loc2], max(start_x, jobs[locx].first) + jobs[locx].d + dist(locx, loc2));
  1039.                 ok &= (start_2[loc2] <= last_start[loc2]);// && start_x <= jobs[locx].last);
  1040.                 //dprint(pos, iw, loc1, loc2, t1, start2_new);
  1041.                 //dprint(last_start[loc2], jobs[locx].last);
  1042.             }
  1043.             if(ok)
  1044.                 valid_pos.push_back(pos);
  1045.         }
  1046.  
  1047.         auto &w = br.shift[pos];
  1048.         {
  1049.             int loc2 = w.loc;
  1050.             int iw = w.iw;
  1051.             for(int i=0; i<jobs[loc2].p; ++i)
  1052.             {
  1053.                 ++pos_idx[iw];
  1054.                 //dprint(iw, pos, br.shift.size(), pos_idx[iw], wpos[iw][pos_idx[iw]], loc2);
  1055.                 assert(pos_idx[iw]+1 < wpos[iw].size());
  1056.                 assert(wpos[iw][pos_idx[iw]] == loc2);
  1057.                 ++iw;
  1058.             }
  1059.         }
  1060.     }
  1061.  
  1062.     return valid_pos;
  1063. }
  1064.  
  1065.  
  1066. void convert(const vector<Worker> &ww, vector<Brigade> &brigades)
  1067. {
  1068.     for(const Worker &w : ww)
  1069.     {
  1070.         int p = 0;
  1071.         for(int i=1; i+1<w.locs.size(); ++i)
  1072.             p = max(p, jobs[w.locs[i]].p);
  1073.         brigades.push_back(Brigade());
  1074.         brigades.back().size = p;
  1075.         for(int loc : w.locs)
  1076.         {
  1077.             brigades.back().shift.push_back( W(loc,0) );
  1078.         }
  1079.     }
  1080. }
  1081.  
  1082. void make2()
  1083. {
  1084.     vector<Brigade> brigades;
  1085.     int pp[2048];
  1086.  
  1087.     for(int i=0; i<N; ++i)
  1088.     {
  1089.         pp[i] = jobs[i].p;
  1090.         if(jobs[i].p >= 4)
  1091.             jobs[i].p = 7;
  1092.         //else if(jobs[i].p >= 3)
  1093.             //jobs[i].p = 4;
  1094.         //else if(jobs[i].p >= 1)
  1095.             //jobs[i].p = 2;
  1096.     }
  1097.  
  1098.     greedy(4,7);
  1099.     post(10, false);
  1100.    
  1101.     for(int i=0; i<N; ++i)
  1102.         jobs[i].p = pp[i];
  1103.  
  1104.     convert(workers, brigades);
  1105.    
  1106.     vector<int> idx;
  1107.     for(int i=1; i<N; ++i) if(!jobs[i].done)
  1108.         idx.push_back(i);
  1109.     sort(idx.begin(), idx.end(), [](int a, int b) {
  1110.         return
  1111.             jobs[a].p*(jobs[a].d+30) >
  1112.             jobs[b].p*(jobs[b].d+30);
  1113.         //if(jobs[a].p != jobs[b].p)
  1114.             //return jobs[a].p > jobs[b].p;
  1115.         //return jobs[a].d > jobs[b].d;
  1116.     });
  1117.    
  1118.     int ch = 0;
  1119.     for(int loc : idx) if(1 < jobs[loc].p)
  1120.     {
  1121.         if(!tl.go())
  1122.             break;
  1123.         int best_val = (3 + jobs[loc].p)*jobs[loc].p*jobs[loc].d;
  1124.         Brigade *best_bg = 0;
  1125.         int best_is = -1;
  1126.         int best_iw = -1;
  1127.         for(Brigade &bg : brigades)
  1128.         {
  1129.             int v1 = evaluate_brigade(bg);
  1130.             for(int iw=0; iw+jobs[loc].p <= bg.size; ++iw)
  1131.             {
  1132.                 auto valid_pos = get_valid_inserts(bg, loc, iw);
  1133.                 if(!valid_pos.empty() && valid_pos.back() != bg.shift.size()-1)
  1134.                     valid_pos.push_back(bg.shift.size()-1);
  1135.                 if(!valid_pos.empty() && valid_pos.front() != 1)
  1136.                     valid_pos.push_back(1);
  1137.                
  1138.                 for(int is : valid_pos)
  1139.                 {
  1140.                     bg.shift.insert(bg.shift.begin() + is, W(loc,iw));
  1141.                     int v2 = evaluate_brigade(bg);
  1142.                     //assert(0 <= v2);
  1143.                     bg.shift.erase(bg.shift.begin() + is);
  1144.                    
  1145.                     if(best_val < v2-v1)
  1146.                     {
  1147.                         best_val = v2-v1;
  1148.                         best_bg = &bg;
  1149.                         best_iw = iw;
  1150.                         best_is = is;
  1151.                     }
  1152.                 }
  1153.             }
  1154.         }
  1155.         if(best_bg)
  1156.         {
  1157.             best_bg->shift.insert(best_bg->shift.begin() + best_is, W(loc,best_iw));
  1158.             ch += best_val;
  1159.             jobs[loc].done = true;
  1160.         }
  1161.     }
  1162.     dprint(ch);
  1163.    
  1164.     for(int i=0; i<N; ++i)
  1165.     {
  1166.         pp[i] = jobs[i].p;
  1167.         if(jobs[i].p == 2)
  1168.             jobs[i].p = 3;
  1169.     }
  1170.  
  1171.     workers.clear();
  1172.     greedy(2,3);
  1173.     post(10, false);
  1174.    
  1175.     for(int i=0; i<N; ++i)
  1176.         jobs[i].p = pp[i];
  1177.  
  1178.     convert(workers, brigades);
  1179.     for(int loc : idx) //if(1 < jobs[loc].p)
  1180.     {
  1181.         if(jobs[loc].done)
  1182.             continue;
  1183.         if(!tl.go())
  1184.             break;
  1185.         int best_val = jobs[loc].d;//(2 + jobs[loc].p)*jobs[loc].p*jobs[loc].d;
  1186.         Brigade *best_bg = 0;
  1187.         int best_is = -1;
  1188.         int best_iw = -1;
  1189.         for(Brigade &bg : brigades)
  1190.         {
  1191.             int v1 = evaluate_brigade(bg);
  1192.             for(int iw=0; iw+jobs[loc].p <= bg.size; ++iw)
  1193.             {
  1194.                 auto valid_pos = get_valid_inserts(bg, loc, iw);
  1195.                 if(!valid_pos.empty() && valid_pos.back() != bg.shift.size()-1)
  1196.                     valid_pos.push_back(bg.shift.size()-1);
  1197.                 if(!valid_pos.empty() && valid_pos.front() != 1)
  1198.                     valid_pos.push_back(1);
  1199.                 for(int is : valid_pos)
  1200.                 {
  1201.                     bg.shift.insert(bg.shift.begin() + is, W(loc,iw));
  1202.                     int v2 = evaluate_brigade(bg);
  1203.                     //assert(0 <= v2);
  1204.                     bg.shift.erase(bg.shift.begin() + is);
  1205.                    
  1206.                     if(best_val < v2-v1)
  1207.                     {
  1208.                         best_val = v2-v1;
  1209.                         best_bg = &bg;
  1210.                         best_iw = iw;
  1211.                         best_is = is;
  1212.                     }
  1213.                 }
  1214.             }
  1215.         }
  1216.         if(best_bg)
  1217.         {
  1218.             best_bg->shift.insert(best_bg->shift.begin() + best_is, W(loc,best_iw));
  1219.             ch += best_val;
  1220.             jobs[loc].done = true;
  1221.         }
  1222.     }
  1223.  
  1224.     workers.clear();
  1225.     greedy(1,1);
  1226.     post(10, false);
  1227.    
  1228.     convert(workers, brigades);
  1229.  
  1230.  
  1231.     int s = 0;
  1232.     for(int i=0; i<brigades.size(); ++i)
  1233.     {
  1234.         int v = evaluate_brigade(brigades[i]);
  1235.         if(v <= 0)
  1236.             brigades.erase(brigades.begin()+(i--));
  1237.         else
  1238.             s += v;
  1239.     }
  1240.     //int score = s;
  1241.     dprint(s);
  1242.  
  1243.     write_sol2(brigades);
  1244. }
  1245.  
  1246. int main(int argc, char **arg)
  1247. {
  1248.     ios::sync_with_stdio(false);
  1249.  
  1250. #ifdef _GEN_INPUT  
  1251.     if(1 < argc)
  1252.         srand(atoi(arg[1]));
  1253.     for(int i=0; i<999; ++i)
  1254.         rand();
  1255.     N = 500 + rand()%1501;
  1256. #else
  1257.     cin >> N;
  1258. #endif
  1259.     jobs.resize(N);
  1260.     for(int i=0; i<N; ++i)
  1261.     {
  1262. #ifdef _GEN_INPUT
  1263.         jobs[i].x = random(0,100);
  1264.         jobs[i].y = random(0,100);
  1265.         jobs[i].d = random(5,30);
  1266.         jobs[i].p = random(1,7);
  1267.         do {
  1268.             jobs[i].first = random(200,800);
  1269.             jobs[i].last = random(200,800);
  1270.         } while((jobs[i].last - jobs[i].first) < 60 || (jobs[i].last - jobs[i].first) > 300);
  1271. #else
  1272.         cin >> jobs[i].x >> jobs[i].y >> jobs[i].d >> jobs[i].p >> jobs[i].first >> jobs[i].last;
  1273. #endif
  1274.         if(i == 0)
  1275.             jobs[0].d = jobs[0].p = jobs[0].d = jobs[0].first = jobs[0].last = 0;
  1276.         jobs[i].last -= jobs[i].d;
  1277.         jobs[i].orig_p = jobs[i].p;
  1278.     }
  1279.     jobs[0].last = 9999;
  1280.    
  1281.     srand(4444);
  1282.  
  1283.     make2();
  1284.     workers.clear();
  1285.  
  1286.     return 0;
  1287. }
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