Submission #1062823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062823		Zicrus	Wiring (IOI17_wiring)	C++17	13 / 100	46 ms	12208 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
 
typedef long long ll;

vector<ll> dp;

ll getDp(ll i) {
    if (i < 0) return 0;
    return dp[i];
}

ll n;
vector<pair<ll, pair<ll, ll>>> pos; // pos, {type, id in type}
vector<ll> sumL, sumR;
ll totalDist;

ll solve(ll low, ll high, ll i) {
    ll cntL = high - low + 1;
    ll cntH = i - high;
    ll cutoff = high;
    if (cntL > cntH) cutoff++;
    ll resL = sumR[low] - sumR[high+1] - (totalDist - pos[cutoff].first) * cntL;
    ll resH = sumL[i] - sumL[high] - pos[cutoff].first * cntH;
    return resL + resH;
}

ll min_total_length(vector<int> r, vector<int> b) {
    // Initialize pos
    pos.clear();
    for (int i = 0; i < r.size(); i++) pos.push_back({r[i], {0, i}});
    for (int i = 0; i < b.size(); i++) pos.push_back({b[i], {1, i}});
    sort(pos.begin(), pos.end());
    n = pos.size();
    for (int i = n-1; i >= n; i--) pos[i].first -= pos[0].first;
    totalDist = pos.back().first;

    // Initialize sums
    sumL = vector<ll>(n);
    sumR = vector<ll>(n);
    for (int i = 1; i < n; i++) {
        sumL[i] = sumL[i-1] + pos[i].first;
    }
    for (int i = n-2; i >= 0; i--) {
        sumR[i] = sumR[i+1] + (totalDist - pos[i].first);
    }

    return solve(0, r.size()-1, n-1);
    
    // Run dp
    //dp = vector<ll>(n, 1ll << 62ll);
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < r.size(); i++) pos.push_back({r[i], {0, i}});
      |                     ~~^~~~~~~~~~
wiring.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < b.size(); i++) pos.push_back({b[i], {1, i}});
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45