Submission #73181

#TimeUsernameProblemLanguageResultExecution timeMemory
73181KieranHorganWiring (IOI17_wiring)C++17
100 / 100
361 ms114864 KiB
#pragma GCC optimize("O3") #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+hi)/2; r1 = dp[shash(s-1, m1-1)] + calcWire(s-1, m1, i); m2 = m1+1; 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 (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int s = 0; s < segments.size(); s++) {
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < segments[s].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < segments[s].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < segments[1].size(); j++) {
                 ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int s = 2; s < segments.size(); s++) {
                 ~~^~~~~~~~~~~~~~~~~
wiring.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < segments[s].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:72:59: warning: unused variable 'j' [-Wunused-variable]
    int lo = 1, hi = max(1ll,(int)segments[s-1].size()-1), j, m1, m2, r1, r2;
                                                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...