Submission #285357

#	Time	Username	Problem	Language	Result	Execution time	Memory
285357		A02	Wiring (IOI17_wiring)	C++14	38 / 100	57 ms	8736 KiB

wiring

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

using namespace std;

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

//    for (int i = 0; i < 100; i++){
//        r.push_back(i + 2);
//    }
//
//    for (int j = 0; j < 100; j++){
//        b.push_back(j + 100000000 + 1);
//    }

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

    vector<pair<long long, bool> > all_points;

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

    for (int i = 0; i < M; i++){
        all_points.push_back(make_pair((long long) 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;
                    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;
                    //cout << cp << ' ' << 'a' << best_cost_left[cp] << endl;
                } else {
                    //cout << 'b' << ' ' << left_size << ' ' << right_size endl;
                    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] << ' ' << best_cost_left[cp] - best_cost_left[cp - 1] << 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 += ((long long) max(N, M)) * (all_points[N].first - all_points[N - 1].first);

    //cout << t<< endl;

    //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:67:9: warning: 'block_start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     int block_start;
      |         ^~~~~~~~~~~
wiring.cpp:122:13: warning: 'is_single' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |             if (is_single){
      |             ^~
wiring.cpp:121:23: warning: 'right_size' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |             right_size++;
      |             ~~~~~~~~~~^~
wiring.cpp:132:17: warning: 'left_size' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |                 if (right_size <= left_size){
      |                 ^~
wiring.cpp:62:9: warning: 'left_pointer' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |     int left_pointer;
      |         ^~~~~~~~~~~~

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