Submission #445713

#	Time	Username	Problem	Language	Result	Execution time	Memory
445713		blue	Wiring (IOI17_wiring)	C++17	13 / 100	71 ms	12656 KiB

wiring

#include "wiring.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

/*
Let all the points be sorted together.
color(i) = color of i'th point

A BR wire and a RB wire cannot have any length in common.
So, we can divide the points into clusters, each of which has two 'clumps' of points.


Consider clusters of homogeneous points.

*/
vector<int> R, B;
int N, M;

vector<int> S;
vector< vector<long long> > X;
vector< vector<long long> > Xsum;

const long long INF = 1'000'000'000'000'000'000LL;

long long get_score(int i, int p1, int p2)
{
    long long size1 = S[i] - p1 + 1;
    long long size2 = p2;

    // cerr << "size ";

    // cerr << size1 << ' ' << size2 << '\n';

    long long ans = Xsum[i+1][size2]  -  (Xsum[i][S[i]] - Xsum[i][S[i] - size1]);

    // cerr << "ans = " <<  ans << '\n';
    // cerr << X[i+1][1] * (size1 - size2) << '\n';

    if(size1 > size2) ans += X[i+1][1] * (size1 - size2);
    else if(size1 < size2) ans -= X[i].back() * (size2 - size1);

    return ans;
}

long long min_total_length(vector<int> r, vector<int> b)
{
//PART 0: GET INPUT AND DIVIDE INTO BLOCKS
    R = r;
    B = b;
    N = R.size();
    M = B.size();

    int I[N+M];
    for(int i = 1; i <= N; i++) I[i-1] = i;
    for(int j = 1; j <= M; j++) I[N+j-1] = -j;
    sort(I, I+N+M, [] (int x, int y)
    {
        int px = x > 0 ? R[x-1] : B[-(x+1)];
        int py = y > 0 ? R[y-1] : B[-(y+1)];
        return px < py;
    });


    for(int j = 0; j < N+M; j++)
    {
        // cerr << "j = " << I[j] << '\n';

        int new_vector = (j == 0 || ((I[j] > 0) != (I[j-1] > 0)));

        if(new_vector)
        {
            S.push_back(0);
            X.push_back(vector<long long>(1, 0));
        }

        int i = I[j];
        X.back().push_back(i > 0 ? R[i-1] : B[-(i+1)]);
        S[S.size()-1]++;
    }

    Xsum = X;
    for(int i = 0; i < X.size(); i++)
    {
        for(int j = 1; j < X[i].size(); j++)
        {
            Xsum[i][j] += Xsum[i][j-1];
        }
        // cerr << i << ' ' << S[i] << ": ";
        // for(int j = 0; j < X[i].size(); j++) cerr << X[i][j] << ' ';
        // cerr << "| ";
        // for(int j = 0; j < Xsum[i].size(); j++) cerr << Xsum[i][j] << ' ';
        // cerr << '\n';
    }

    // cerr << get_score(6, 2, 1) << '\n';

    vector<long long> res[X.size()];

    res[0] = vector<long long>(X[0].size());
    for(int j = 1; j < res[0].size(); j++)
        res[0][j] = INF;

    res[1] = vector<long long>(X[1].size());
    res[1][0] = INF;
    for(int j = 1; j < res[1].size(); j++)
        res[1][j] = get_score(0, 1, j);

    // cerr << "yes\n";

    for(int i = 2; i < X.size(); i++)
    {
        res[i] = vector<long long>(X[i].size());
        res[i][0] = res[i-1].back();

        int j1 = 1;
        for(int j = 1; j < res[i].size(); j++)
        {
            while(j1+1 < res[i-1].size() && res[i-1][j1-1] + get_score(i-1, j1, j) > res[i-1][j1] + get_score(i-1, j1+1, j))
                j1++;

            res[i][j] = res[i-1][j1-1] + get_score(i-1, j1, j);
        }
    }

    return res[X.size()-1].back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0; i < X.size(); i++)
      |                    ~~^~~~~~~~~~
wiring.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int j = 1; j < X[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~
wiring.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int j = 1; j < res[0].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
wiring.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int j = 1; j < res[1].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
wiring.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 2; i < X.size(); i++)
      |                    ~~^~~~~~~~~~
wiring.cpp:118:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int j = 1; j < res[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~
wiring.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             while(j1+1 < res[i-1].size() && res[i-1][j1-1] + get_score(i-1, j1, j) > res[i-1][j1] + get_score(i-1, j1+1, j))
      |                   ~~~~~^~~~~~~~~~~~~~~~~

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