• API
• FAQ
• Tools
• Archive
SHARE
TWEET # VRt Contest Codeforces a guest May 14th, 2019 210 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) {
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.
97.             if (!debug) {
98.                 answer_line = "start " + to_string(time) + " 1";
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.
117.                 if (!debug) {
118.                     answer_line = "arrive " + to_string(arrive_time) + " " + to_string(job.num);
120.                     answer_line = "work " + to_string(arrive_time) + " " + to_string(arrive_time + job.d) + " " + to_string(job.num);
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.
134.             if (!debug) {
135.                 answer_line = "arrive " + to_string(time + dist(prev, base)) + " 1";
137.                 answer_line = "end";
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.

Top