Submission #298924

#	Time	Username	Problem	Language	Result	Execution time	Memory
298924		infinite_iq	Wiring (IOI17_wiring)	C++14	13 / 100	37 ms	5376 KiB

wiring

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef vector < int > vi ;
#define lb lower_bound
#include "wiring.h"
ll Solve1 ( vi a , vi b ) {
        ll cost = 0 ;
        for ( int i = 0 ; i < a .size () ; i ++ ) {
                cost += abs ( a [i] - b [i] ) ;
        }
        for ( int i = a .size () ; i < b .size () ; i ++ ) {
                ll ret = 1e18 ;
                auto it = lb ( a .begin () , a .end () , b [i] ) - a .begin () ;
                if ( it != a .size () ) {
                        ret = min ( ret , (ll) ( abs ( b [i] - a [it] ) ) ) ;
                }
                it -- ;
                if ( it != -1 ) {
                        ret = min ( ret , (ll) ( abs ( b [i] - a [it] ) ) ) ;
                }
                cost += ret ;
        }
        return cost ;
}
ll Solve2 ( vi a , vi b ) {
        ll cost = 0 , more = b .size () - a .size () ;
        for ( int i = 0 ; i < a .size () ; i ++ ) {
                cost += abs ( a [i] - b [i+more] ) ;
        }
        for ( int i = 0 ; i < more ; i ++ ) {
                ll ret = 1e18 ;
                auto it = lb ( a .begin () , a .end () , b [i] ) - a .begin () ;
                if ( it != a .size () ) {
                        ret = min ( ret , (ll) ( abs ( b [i] - a [it] ) ) ) ;
                }
                it -- ;
                if ( it != -1 ) {
                        ret = min ( ret , (ll) ( abs ( b [i] - a [it] ) ) ) ;
                }
                cost += ret ;
        }
        return cost ;
}
long long min_total_length ( vi a , vi b ) {
        if ( a .size () > b .size () ) swap ( a , b ) ;
        return min ( Solve1 ( a , b ) , Solve2 ( a , b ) ) ;
}

Compilation message (stderr)

wiring.cpp: In function 'll Solve1(vi, vi)':
wiring.cpp:9:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |         for ( int i = 0 ; i < a .size () ; i ++ ) {
      |                           ~~^~~~~~~~~~~~
wiring.cpp:12:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for ( int i = a .size () ; i < b .size () ; i ++ ) {
      |                                    ~~^~~~~~~~~~~~
wiring.cpp:15:25: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |                 if ( it != a .size () ) {
      |                      ~~~^~~~~~~~~~~~~
wiring.cpp: In function 'll Solve2(vi, vi)':
wiring.cpp:28:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for ( int i = 0 ; i < a .size () ; i ++ ) {
      |                           ~~^~~~~~~~~~~~
wiring.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 if ( it != a .size () ) {
      |                      ~~~^~~~~~~~~~~~~

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