#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, ans;
vector<int> fullList;
unordered_map<int, bool> isRed, isBlue;
vector<vector<int>> segments;
vector<vector<int>> prefixR;
vector<vector<int>> prefixL;
int calcWire(int s, int l, int r) {
int res = 0;
res += prefixL[s][l];
res += (segments[s].size()-l) * (segments[s+1][0]-segments[s].back());
res += prefixR[s+1][r];
res += (r+1) * (segments[s+1][0]-segments[s].back());
res -= min((int)segments[s].size()-l, r+1)*(segments[s+1][0]-segments[s].back());
return res;
}
int shash(int a, int b) {
return a*1000000 + b;
}
unordered_map<int, int> dp;
long long min_total_length(vector<signed> r, vector<signed> b) {
dp.reserve(32768); dp.max_load_factor(0.25);
n = r.size();
m = b.size();
fullList.resize(n+m);
merge(r.begin(), r.end(), b.begin(), b.end(), fullList.begin());
for(auto x: r)
isRed[x]=1;
for(auto x: b)
isBlue[x]=1;
for(int i = 0; i < m+n; i++) {
if(i==0 || isRed[fullList[i]] != isRed[fullList[i-1]]) {
segments.push_back(vector<int>(0));
prefixL.push_back(vector<int>(0));
prefixR.push_back(vector<int>(0));
segments.back().push_back(fullList[i]);
} else {
segments.back().push_back(fullList[i]);
}
}
for(int s = 0; s < segments.size(); s++) {
prefixR[s].push_back(0);
for(int i = 1; i < segments[s].size(); i++)
prefixR[s].push_back(prefixR[s][i-1]+segments[s][i]-segments[s][0]);
reverse(segments[s].begin(), segments[s].end());
prefixL[s].push_back(0);
for(int i = 1; i < segments[s].size(); i++)
prefixL[s].push_back(prefixL[s][i-1]+segments[s][0]-segments[s][i]);
reverse(prefixL[s].begin(), prefixL[s].end());
reverse(segments[s].begin(), segments[s].end());
}
for(int j = 0; j < segments[1].size(); j++) {
dp[shash(1,j)] = calcWire(0, 0, j);
}
for(int s = 2; s < segments.size(); s++) {
for(int i = 0; i < segments[s].size(); i++) {
dp[shash(s, i)] = dp[shash(s-1, 0)] + calcWire(s-1, 0, i);
if(dp[shash(s-2, segments[s-2].size()-1)] != 0)
dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-2, segments[s-2].size()-1)] + calcWire(s-1, 0, i));
int lo = 1, hi = max(1ll,(int)segments[s-1].size()-1), j, m1, m2, r1, r2;
while(lo+1 < hi) {
m1 = (lo+lo+hi)/3;
r1 = dp[shash(s-1, m1-1)] + calcWire(s-1, m1, i);
m2 = (lo+hi+hi)/3;
r2 = dp[shash(s-1, m2-1)] + calcWire(s-1, m2, i);
if(r1==r2)
lo = m1, hi = m2;
else if(r1 < r2)
hi = m2-1;
else
lo = m1+1;
}
dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-1, lo-1)] + calcWire(s-1, lo, i));
dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-1, hi-1)] + calcWire(s-1, hi, i));
// cerr << s << " " << i << ": " << dp[shash(s, i)] << endl;
}
}
return dp[shash(segments.size()-1, segments.back().size()-1)];
if(segments.size() == 2)
return calcWire(0, 0, m-1);
return -1;
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int s = 0; s < segments.size(); s++) {
~~^~~~~~~~~~~~~~~~~
wiring.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < segments[s].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < segments[s].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < segments[1].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int s = 2; s < segments.size(); s++) {
~~^~~~~~~~~~~~~~~~~
wiring.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < segments[s].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:71:59: warning: unused variable 'j' [-Wunused-variable]
int lo = 1, hi = max(1ll,(int)segments[s-1].size()-1), j, m1, m2, r1, r2;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
704 KB |
Output is correct |
3 |
Correct |
3 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
812 KB |
Output is correct |
5 |
Correct |
2 ms |
812 KB |
Output is correct |
6 |
Correct |
2 ms |
812 KB |
Output is correct |
7 |
Correct |
2 ms |
916 KB |
Output is correct |
8 |
Correct |
3 ms |
916 KB |
Output is correct |
9 |
Correct |
3 ms |
916 KB |
Output is correct |
10 |
Correct |
3 ms |
996 KB |
Output is correct |
11 |
Correct |
2 ms |
996 KB |
Output is correct |
12 |
Correct |
3 ms |
996 KB |
Output is correct |
13 |
Correct |
3 ms |
996 KB |
Output is correct |
14 |
Correct |
4 ms |
996 KB |
Output is correct |
15 |
Correct |
3 ms |
996 KB |
Output is correct |
16 |
Correct |
3 ms |
996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
996 KB |
Output is correct |
2 |
Correct |
3 ms |
996 KB |
Output is correct |
3 |
Correct |
131 ms |
19344 KB |
Output is correct |
4 |
Correct |
108 ms |
19344 KB |
Output is correct |
5 |
Correct |
136 ms |
25584 KB |
Output is correct |
6 |
Correct |
159 ms |
29120 KB |
Output is correct |
7 |
Correct |
173 ms |
29244 KB |
Output is correct |
8 |
Correct |
159 ms |
29244 KB |
Output is correct |
9 |
Correct |
162 ms |
29244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
29244 KB |
Output is correct |
2 |
Correct |
3 ms |
29244 KB |
Output is correct |
3 |
Correct |
310 ms |
46700 KB |
Output is correct |
4 |
Correct |
277 ms |
46700 KB |
Output is correct |
5 |
Correct |
2 ms |
46700 KB |
Output is correct |
6 |
Correct |
2 ms |
46700 KB |
Output is correct |
7 |
Correct |
4 ms |
46700 KB |
Output is correct |
8 |
Correct |
3 ms |
46700 KB |
Output is correct |
9 |
Correct |
2 ms |
46700 KB |
Output is correct |
10 |
Correct |
2 ms |
46700 KB |
Output is correct |
11 |
Correct |
2 ms |
46700 KB |
Output is correct |
12 |
Correct |
2 ms |
46700 KB |
Output is correct |
13 |
Correct |
2 ms |
46700 KB |
Output is correct |
14 |
Correct |
2 ms |
46700 KB |
Output is correct |
15 |
Correct |
2 ms |
46700 KB |
Output is correct |
16 |
Correct |
2 ms |
46700 KB |
Output is correct |
17 |
Correct |
2 ms |
46700 KB |
Output is correct |
18 |
Correct |
291 ms |
46700 KB |
Output is correct |
19 |
Correct |
299 ms |
46700 KB |
Output is correct |
20 |
Correct |
279 ms |
46700 KB |
Output is correct |
21 |
Correct |
305 ms |
46700 KB |
Output is correct |
22 |
Correct |
308 ms |
46700 KB |
Output is correct |
23 |
Correct |
359 ms |
46700 KB |
Output is correct |
24 |
Correct |
390 ms |
46700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
46700 KB |
Output is correct |
2 |
Correct |
321 ms |
46700 KB |
Output is correct |
3 |
Correct |
240 ms |
46700 KB |
Output is correct |
4 |
Correct |
266 ms |
46700 KB |
Output is correct |
5 |
Correct |
256 ms |
46700 KB |
Output is correct |
6 |
Correct |
3 ms |
46700 KB |
Output is correct |
7 |
Correct |
2 ms |
46700 KB |
Output is correct |
8 |
Correct |
2 ms |
46700 KB |
Output is correct |
9 |
Correct |
2 ms |
46700 KB |
Output is correct |
10 |
Correct |
3 ms |
46700 KB |
Output is correct |
11 |
Correct |
3 ms |
46700 KB |
Output is correct |
12 |
Correct |
3 ms |
46700 KB |
Output is correct |
13 |
Correct |
2 ms |
46700 KB |
Output is correct |
14 |
Correct |
3 ms |
46700 KB |
Output is correct |
15 |
Correct |
2 ms |
46700 KB |
Output is correct |
16 |
Correct |
2 ms |
46700 KB |
Output is correct |
17 |
Correct |
2 ms |
46700 KB |
Output is correct |
18 |
Correct |
270 ms |
46700 KB |
Output is correct |
19 |
Correct |
320 ms |
46700 KB |
Output is correct |
20 |
Correct |
299 ms |
46700 KB |
Output is correct |
21 |
Correct |
301 ms |
46700 KB |
Output is correct |
22 |
Correct |
205 ms |
46700 KB |
Output is correct |
23 |
Correct |
184 ms |
46700 KB |
Output is correct |
24 |
Correct |
179 ms |
46700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
704 KB |
Output is correct |
3 |
Correct |
3 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
812 KB |
Output is correct |
5 |
Correct |
2 ms |
812 KB |
Output is correct |
6 |
Correct |
2 ms |
812 KB |
Output is correct |
7 |
Correct |
2 ms |
916 KB |
Output is correct |
8 |
Correct |
3 ms |
916 KB |
Output is correct |
9 |
Correct |
3 ms |
916 KB |
Output is correct |
10 |
Correct |
3 ms |
996 KB |
Output is correct |
11 |
Correct |
2 ms |
996 KB |
Output is correct |
12 |
Correct |
3 ms |
996 KB |
Output is correct |
13 |
Correct |
3 ms |
996 KB |
Output is correct |
14 |
Correct |
4 ms |
996 KB |
Output is correct |
15 |
Correct |
3 ms |
996 KB |
Output is correct |
16 |
Correct |
3 ms |
996 KB |
Output is correct |
17 |
Correct |
2 ms |
996 KB |
Output is correct |
18 |
Correct |
3 ms |
996 KB |
Output is correct |
19 |
Correct |
131 ms |
19344 KB |
Output is correct |
20 |
Correct |
108 ms |
19344 KB |
Output is correct |
21 |
Correct |
136 ms |
25584 KB |
Output is correct |
22 |
Correct |
159 ms |
29120 KB |
Output is correct |
23 |
Correct |
173 ms |
29244 KB |
Output is correct |
24 |
Correct |
159 ms |
29244 KB |
Output is correct |
25 |
Correct |
162 ms |
29244 KB |
Output is correct |
26 |
Correct |
2 ms |
29244 KB |
Output is correct |
27 |
Correct |
3 ms |
29244 KB |
Output is correct |
28 |
Correct |
310 ms |
46700 KB |
Output is correct |
29 |
Correct |
277 ms |
46700 KB |
Output is correct |
30 |
Correct |
2 ms |
46700 KB |
Output is correct |
31 |
Correct |
2 ms |
46700 KB |
Output is correct |
32 |
Correct |
4 ms |
46700 KB |
Output is correct |
33 |
Correct |
3 ms |
46700 KB |
Output is correct |
34 |
Correct |
2 ms |
46700 KB |
Output is correct |
35 |
Correct |
2 ms |
46700 KB |
Output is correct |
36 |
Correct |
2 ms |
46700 KB |
Output is correct |
37 |
Correct |
2 ms |
46700 KB |
Output is correct |
38 |
Correct |
2 ms |
46700 KB |
Output is correct |
39 |
Correct |
2 ms |
46700 KB |
Output is correct |
40 |
Correct |
2 ms |
46700 KB |
Output is correct |
41 |
Correct |
2 ms |
46700 KB |
Output is correct |
42 |
Correct |
2 ms |
46700 KB |
Output is correct |
43 |
Correct |
291 ms |
46700 KB |
Output is correct |
44 |
Correct |
299 ms |
46700 KB |
Output is correct |
45 |
Correct |
279 ms |
46700 KB |
Output is correct |
46 |
Correct |
305 ms |
46700 KB |
Output is correct |
47 |
Correct |
308 ms |
46700 KB |
Output is correct |
48 |
Correct |
359 ms |
46700 KB |
Output is correct |
49 |
Correct |
390 ms |
46700 KB |
Output is correct |
50 |
Correct |
3 ms |
46700 KB |
Output is correct |
51 |
Correct |
321 ms |
46700 KB |
Output is correct |
52 |
Correct |
240 ms |
46700 KB |
Output is correct |
53 |
Correct |
266 ms |
46700 KB |
Output is correct |
54 |
Correct |
256 ms |
46700 KB |
Output is correct |
55 |
Correct |
3 ms |
46700 KB |
Output is correct |
56 |
Correct |
2 ms |
46700 KB |
Output is correct |
57 |
Correct |
2 ms |
46700 KB |
Output is correct |
58 |
Correct |
2 ms |
46700 KB |
Output is correct |
59 |
Correct |
3 ms |
46700 KB |
Output is correct |
60 |
Correct |
3 ms |
46700 KB |
Output is correct |
61 |
Correct |
3 ms |
46700 KB |
Output is correct |
62 |
Correct |
2 ms |
46700 KB |
Output is correct |
63 |
Correct |
3 ms |
46700 KB |
Output is correct |
64 |
Correct |
2 ms |
46700 KB |
Output is correct |
65 |
Correct |
2 ms |
46700 KB |
Output is correct |
66 |
Correct |
2 ms |
46700 KB |
Output is correct |
67 |
Correct |
270 ms |
46700 KB |
Output is correct |
68 |
Correct |
320 ms |
46700 KB |
Output is correct |
69 |
Correct |
299 ms |
46700 KB |
Output is correct |
70 |
Correct |
301 ms |
46700 KB |
Output is correct |
71 |
Correct |
205 ms |
46700 KB |
Output is correct |
72 |
Correct |
184 ms |
46700 KB |
Output is correct |
73 |
Correct |
179 ms |
46700 KB |
Output is correct |
74 |
Correct |
202 ms |
46700 KB |
Output is correct |
75 |
Correct |
293 ms |
46700 KB |
Output is correct |
76 |
Correct |
281 ms |
46700 KB |
Output is correct |
77 |
Correct |
315 ms |
47836 KB |
Output is correct |
78 |
Correct |
298 ms |
49288 KB |
Output is correct |
79 |
Correct |
416 ms |
50696 KB |
Output is correct |
80 |
Correct |
229 ms |
50696 KB |
Output is correct |
81 |
Correct |
240 ms |
50696 KB |
Output is correct |
82 |
Correct |
169 ms |
50696 KB |
Output is correct |
83 |
Correct |
228 ms |
50696 KB |
Output is correct |
84 |
Correct |
222 ms |
50696 KB |
Output is correct |
85 |
Correct |
455 ms |
60404 KB |
Output is correct |
86 |
Correct |
247 ms |
60404 KB |
Output is correct |
87 |
Correct |
253 ms |
60404 KB |
Output is correct |
88 |
Correct |
348 ms |
66180 KB |
Output is correct |
89 |
Correct |
259 ms |
68004 KB |
Output is correct |
90 |
Correct |
326 ms |
69820 KB |
Output is correct |
91 |
Correct |
239 ms |
69820 KB |
Output is correct |
92 |
Correct |
386 ms |
74104 KB |
Output is correct |
93 |
Correct |
236 ms |
74104 KB |
Output is correct |
94 |
Correct |
353 ms |
77692 KB |
Output is correct |
95 |
Correct |
358 ms |
79560 KB |
Output is correct |
96 |
Correct |
248 ms |
79560 KB |
Output is correct |
97 |
Correct |
196 ms |
79560 KB |
Output is correct |
98 |
Correct |
239 ms |
79560 KB |
Output is correct |
99 |
Correct |
230 ms |
79560 KB |
Output is correct |
100 |
Correct |
413 ms |
89468 KB |
Output is correct |
101 |
Correct |
212 ms |
89468 KB |
Output is correct |
102 |
Correct |
290 ms |
89468 KB |
Output is correct |