Submission #1059917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059917		Zicrus	Wiring (IOI17_wiring)	C++17	13 / 100	28 ms	12844 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
 
typedef long long ll;
 
ll min_total_length(vector<int> r, vector<int> b) {
	vector<vector<int>> rb = {r, b};
    vector<pair<ll, pair<ll, ll>>> pos; // pos, {type, id in type}
    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());
    ll n = pos.size();
 
    vector<int> last(2, -1);
    vector<int> nxt(2, 1);
    vector<int> closeNxt(2, -1);
    vector<bool> vst(n);
    ll res = 0;
    for (int i = 0; i < n; i++) {
        if (vst[i]) continue;
 
        ll otherT = pos[i].second.first ^ 1;
        while (nxt[otherT] < n && (vst[nxt[otherT]] || pos[nxt[otherT]].second.first != otherT)) nxt[otherT]++;
        while (closeNxt[otherT] < n && (closeNxt[otherT] <= i || pos[closeNxt[otherT]].second.first != otherT)) closeNxt[otherT]++;
        if (nxt[otherT] >= n) {
            if (last[otherT] != -1) {
                res += pos[i].first - last[otherT];
            }
            else {
                res += pos[closeNxt[otherT]].first - pos[i].first;
            }
        }
        else {
            res += pos[nxt[otherT]].first - pos[i].first;
            vst[nxt[otherT]] = true;
        }
 
        vst[i] = true;
        last[pos[i].second.first] = pos[i].first;
    }
 
    return res;
}

Compilation message (stderr)

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