Submission #240308

#	Time	Username	Problem	Language	Result	Execution time	Memory
240308		Ruxandra985	Wiring (IOI17_wiring)	C++14	13 / 100	46 ms	5016 KiB

wiring

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

vector <pair <int,int> > v;
pair <int,int> st[200010];


long long min_total_length(vector<int> r, vector<int> b) {
    int i , curr , j , elem = 0 , val , tip , stg , dr , mid;
    long long sol = 0 , val1 , val2;

    i = j = 0;

    while (i < r.size() && j < b.size()){
        if (r[i] < b[j])
            v.push_back(make_pair(r[i] , 0)) , i++;
        else
            v.push_back(make_pair(b[j] , 1)) , j++;
    }

    while (i < r.size()){
        v.push_back(make_pair(r[i] , 0)) , i++;
    }

    while (j < b.size()){
        v.push_back(make_pair(b[j] , 1)) , j++;
    }

    /// v e vectorul interclasat

    elem = 0;

    for (i = 0 ; i < v.size() ; i++){

        if (elem && st[elem].second != v[i].second){

            sol = sol + v[i].first - st[elem].first;
            elem--;

        }
        else st[++elem] = v[i];


    }

    /// vezi cum cuplezi ce a mai ramas in st

    for (i = 1 ; i <= elem ; i++){
        val = st[i].first;
        tip = st[i].second;
        if (tip == 0){

            stg = 0;
            dr = b.size() - 1;
            while (stg <= dr){
                mid = (stg + dr) / 2;
                if (b[mid] <= val)
                    stg = mid + 1;
                else dr = mid - 1;

            }

            /// dr e cel mai mare elem <= val

            if (dr >= 0){
                val1 = val - b[dr];
            }
            else val1 = INF;

            if (dr + 1 < b.size()){
                val2 = b[dr + 1] - val;
            }
            else val2 = INF;

            sol = sol + min(val1 , val2);


        }
        else {


            stg = 0;
            dr = r.size() - 1;
            while (stg <= dr){
                mid = (stg + dr) / 2;
                if (r[mid] <= val)
                    stg = mid + 1;
                else dr = mid - 1;

            }

            /// dr e cel mai mare elem <= val

            if (dr >= 0){
                val1 = val - r[dr];
            }
            else val1 = INF;

            if (dr + 1 < r.size()){
                val2 = r[dr + 1] - val;
            }
            else val2 = INF;

            sol = sol + min(val1 , val2);


        }
    }

	return sol;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:16:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < r.size() && j < b.size()){
            ~~^~~~~~~~~~
wiring.cpp:16:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < r.size() && j < b.size()){
                            ~~^~~~~~~~~~
wiring.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < r.size()){
            ~~^~~~~~~~~~
wiring.cpp:27:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (j < b.size()){
            ~~^~~~~~~~~~
wiring.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v.size() ; i++){
                  ~~^~~~~~~~~~
wiring.cpp:72:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (dr + 1 < b.size()){
                 ~~~~~~~^~~~~~~~~~
wiring.cpp:101:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (dr + 1 < r.size()){
                 ~~~~~~~^~~~~~~~~~
wiring.cpp:11:13: warning: unused variable 'curr' [-Wunused-variable]
     int i , curr , j , elem = 0 , val , tip , stg , dr , mid;
             ^~~~

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