Submission #1009332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009332		IS_Rushdi	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	436 KiB

wiring

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


long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size();
    int m = b.size();
    long long ans = 0;
    vector<pair<int,int>>m1(n),m2(m);
    for(int i = 0; i < n; i++){
        int nxt = lower_bound(b.begin(), b.end(), r[i]) - b.begin();
        int mn = 2e9;
        int idx = nxt;
        if(nxt != m) mn = b[nxt] - r[i];
        nxt--;
        if(nxt >= 0 && r[i] - b[nxt] < mn){
            mn = r[i] - b[nxt];
            idx = nxt-1;
        }
        m1[i] = {mn,idx};
    }
    for(int i = 0; i < m; i++){
        int nxt = lower_bound(r.begin(),r.end(), b[i]) - r.begin();
        int mn = 2e9;
        int idx = nxt;
        if(nxt != m) mn = r[nxt] - b[i];
        nxt--;
        if(nxt >= 0 && b[i] - r[nxt] < mn){
            mn = b[i] - r[nxt];
            idx = nxt-1;
        }
        m2[i] = {mn,idx};
    }

    int i = 0,j=0;
    while(i < n && j < m){
        if(abs(r[i]-b[j]) < m1[i].first + m2[j].first){
            ans += abs(r[i]-b[j]);
            i++,j++;
        }else{
            ans += m1[i].first;
            i++;
        }
    }
    while(i < n) ans += m1[i++].first;
    while(j < m) ans += m2[j++].first;
    
	return ans;
}

// int main(){
//     cout << min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10}) << '\n';
// }

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