Submission #285351

#	Time	Username	Problem	Language	Result	Execution time	Memory
285351		A02	Wiring (IOI17_wiring)	C++14	0 / 100	43 ms	4460 KiB

wiring

#include<bits/stdc++.h>
#include "wiring.h"

using namespace std;

long long min_total_length(vector<int> r, vector<int> b) {


    int N = r.size();
    int M = b.size();
    long long BIG = ((long long) INT_MAX) * (long long) 200000;

    vector<pair<int, bool> > all_points;

    for (int i = 0; i < N; i++){
        all_points.push_back(make_pair(r[i], true));
    }

    for (int i = 0; i < M; i++){
        all_points.push_back(make_pair(b[i], false));
    }

    sort(all_points.begin(), all_points.end());

    vector<int> block_number (N + M, 0);
    vector<bool> is_single_block (N + M, false);

    for (int i = 1; i < N + M; i++){
        if(all_points[i].second == all_points[i - 1].second){
            block_number[i] = block_number[i - 1];
        } else {
            block_number[i] = block_number[i - 1] + 1;
        }
    }

    if (block_number[0] != block_number[1]){
        is_single_block[0] = true;
    }
    if (block_number[N + M - 1] != block_number[N + M - 2]){
        is_single_block[N + M - 1] = true;
    }
    for (int i = 1; i < N + M - 1; i++){

        if(block_number[i - 1] != block_number[i] && block_number[i + 1] != block_number[i]){
            is_single_block[i] = true;
        }
    }

    vector<long long> best_cost_left (N + M, BIG);

    int current_point = 0;
    while(block_number[current_point] == 0){
        current_point++;
    }
    int left_pointer;
    int left_size;
    int right_size;
    long long partial;
    bool is_single;
    int block_start;

    for (int cp = current_point; cp < N + M; cp++){

        if (block_number[cp] != block_number[cp - 1]){
            left_pointer = cp - 1;
            left_size = 1;
            right_size = 1;
            partial = 0;
            is_single = is_single_block[left_pointer];
            block_start = cp;

            if (is_single){
                partial += all_points[cp].first - all_points[left_pointer].first;
                if (left_pointer == 0){
                    best_cost_left[cp] = min(best_cost_left[cp], partial);
                } else {
                    best_cost_left[cp] = min(best_cost_left[cp], partial + min(best_cost_left[left_pointer], best_cost_left[left_pointer - 1]));
                }
            } else {

                if (block_number[left_pointer] == 0){

                    left_pointer = 0;
                    for (int i = 0; i < cp; i++){
                        partial += all_points[cp].first - all_points[i].first;
                    }
                    left_size = cp - 1;
                    best_cost_left[cp] = partial;
                } else {

                    best_cost_left[cp] = best_cost_left[left_pointer - 1] + all_points[cp].first - all_points[left_pointer].first;
                    partial = all_points[cp].first - all_points[left_pointer].first;
                    //cout << cp << ' ' << best_cost_left[cp] << endl;
                    while (left_pointer > 0 && block_number[left_pointer - 1] == block_number[left_pointer]){

                        if (all_points[cp].first - all_points[left_pointer - 1].first + partial + best_cost_left[left_pointer - 2] <= best_cost_left[cp]){
                            partial += all_points[cp].first - all_points[left_pointer - 1].first;
                            //cout << 'p' << partial << ' ' << left_pointer << endl;
                            left_pointer--;
                            left_size++;
                            best_cost_left[cp] = partial + best_cost_left[left_pointer - 1];
                            //cout << ' ' << best_cost_left[cp] << endl;
                        } else {
                            break;
                        }

                    }
                }

            }

        } else {
            //cout << cp << 'c' << best_cost_left[cp - 1] << endl;
            right_size++;
            if (is_single){
                partial += all_points[cp].first - all_points[left_pointer].first;
                if (left_pointer == 0){
                    best_cost_left[cp] = min(best_cost_left[cp], partial);
                } else {
                    best_cost_left[cp] = min(best_cost_left[cp], partial + min(best_cost_left[left_pointer], best_cost_left[left_pointer - 1]));
                }
            } else {

                best_cost_left[cp] = best_cost_left[cp - 1];
                if (right_size <= left_size){
                    best_cost_left[cp] += all_points[cp].first - all_points[block_start].first;
                } else {
                    best_cost_left[cp] += all_points[cp].first - all_points[block_start - 1].first;
                }

                while (left_pointer > 0 && block_number[left_pointer - 1] == block_number[left_pointer]){

                    long long reduced = best_cost_left[cp];

                    if (right_size >= left_size + 1){
                        reduced = reduced + all_points[block_start - 1].first - all_points[left_pointer - 1].first;
                    } else {
                        reduced = reduced + all_points[block_start].first - all_points[left_pointer - 1].first;
                    }

                    if (reduced + best_cost_left[left_pointer - 2] <= best_cost_left[cp]){
                        best_cost_left[cp] = reduced + best_cost_left[left_pointer - 2];
                        left_size++;
                        left_pointer--;
                    } else {
                        break;
                    }

                }

            }


        }

        //cout << cp << 'f' << best_cost_left[cp] << endl;
    }

    long long t = 0;
    for (int i = 0; i < N; i++){
        t += all_points[N - 1].first - all_points[i].first;
    }
    for (int j = N; j < N + M; j++){
        t += all_points[j].first - all_points[N].first;
    }

    t += max(N, M) * (all_points[N].first - all_points[N - 1].first);

    return t;

    //cout << best_cost_left[N + M - 1] << endl;

	return best_cost_left[N + M - 1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:60:9: warning: 'block_start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     int block_start;
      |         ^~~~~~~~~~~
wiring.cpp:115:13: warning: 'is_single' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |             if (is_single){
      |             ^~
wiring.cpp:114:23: warning: 'right_size' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |             right_size++;
      |             ~~~~~~~~~~^~
wiring.cpp:125:17: warning: 'left_size' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |                 if (right_size <= left_size){
      |                 ^~
wiring.cpp:55:9: warning: 'left_pointer' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     int left_pointer;
      |         ^~~~~~~~~~~~

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