Submission #637318

#	Time	Username	Problem	Language	Result	Execution time	Memory
637318		boris_mihov	Wiring (IOI17_wiring)	C++17	13 / 100	49 ms	8488 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 100000 + 10;

std::set <int> s;
long long min_total_length(std::vector <int> r, std::vector <int> b) 
{
    std::sort(r.begin(), r.end());
    std::sort(b.begin(), b.end());
    if (r.size() > b.size()) std::swap(r, b);

    for (const int &i : b)
    {
        s.insert(i);
    }

    llong ans = 0;
    for (const int &i : r)
    {
        auto it = s.upper_bound(i);
        auto left = it; left--;
        if (it == s.end())
        {
            ans += abs(*left - i);
            s.erase(left);
        } else if (left == s.end())
        {
            ans += abs(*it - i);
            s.erase(it);
        } else
        {
            if (abs(*left - i) <= abs(*it - i))
            {
                ans += abs(*left - i);
                s.erase(left);
            } else
            {
                ans += abs(*it - i);
                s.erase(it);
            }
        }
    }

    int ptr = 0;
    for (const int &i : s)
    {
        while (ptr + 1 != r.size() && r[ptr + 1] <= i) ptr++;
        int currMin = abs(i - r[ptr]);
        if (ptr + 1 != r.size()) currMin = std::min(currMin, abs(r[ptr + 1] - i));
        ans += currMin;
    }

	return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while (ptr + 1 != r.size() && r[ptr + 1] <= i) ptr++;
      |                ~~~~~~~~^~~~~~~~~~~
wiring.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (ptr + 1 != r.size()) currMin = std::min(currMin, abs(r[ptr + 1] - i));
      |             ~~~~~~~~^~~~~~~~~~~

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