Submission #249930

#	Time	Username	Problem	Language	Result	Execution time	Memory
249930		stoyan_malinin	Wiring (IOI17_wiring)	C++14	13 / 100	49 ms	7528 KiB

wiring

#include "wiring.h"
//#include "grader.cpp"

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 2e5 + 5;
const long long inf = 1e10 + 5;

long long bestMatch[MAXN];

long long min_total_length(vector<int> r, vector<int> b)
{
    vector <pair <int, int>> v;
    for(int x: r) v.push_back({x, 0});
    for(int x: b) v.push_back({x, 1});

    sort(v.begin(), v.end());
    for(int i = 0;i<v.size();i++) bestMatch[i] = inf;

    long long last[2] = {-inf, -inf};
    for(int i = 0;i<v.size();i++)
    {
        bestMatch[i] = min(bestMatch[i], v[i].first-last[v[i].second^1]);
        last[v[i].second] = v[i].first;
    }

    last[0] = last[1] = inf;
    for(int i = v.size()-1;i>=0;i--)
    {
        bestMatch[i] = min(bestMatch[i], last[v[i].second^1]-v[i].first);
        last[v[i].second] = v[i].first;
    }

    long long answer = 0;

    stack <int> st[2];
    last[0] = last[1] = -inf;
    for(int i = 0;i<v.size();i++)
    {
        if(st[v[i].second^1].empty()==false
              && v[i].first-v[st[v[i].second^1].top()].first>bestMatch[st[v[i].second^1].top()]+v[i].first-last[v[i].second^1])
        {
            answer += bestMatch[st[v[i].second^1].top()]+v[i].first-last[v[i].second^1];
            st[v[i].second^1].pop();
        }
        else if(st[v[i].second^1].empty()==false)
        {
            answer += v[i].first - v[st[v[i].second^1].top()].first;
            st[v[i].second^1].pop();
        }
        else
        {
            st[v[i].second].push(i);
        }

        last[v[i].second] = v[i].first;
    }

    while(st[0].empty()==false) answer += bestMatch[ st[0].top() ], st[0].pop();
    while(st[1].empty()==false) answer += bestMatch[ st[1].top() ], st[1].pop();

    //cout << answer << " " << st[0].size() << " " << st[1].size() << '\n';
    return answer;
}
/*
4 5
1 2 3 7
0 4 5 9 10

3 4
1 2 100
3 101 102 103
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v.size();i++) bestMatch[i] = inf;
                   ~^~~~~~~~~
wiring.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v.size();i++)
                   ~^~~~~~~~~
wiring.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v.size();i++)
                   ~^~~~~~~~~

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