Submission #448182

#	Time	Username	Problem	Language	Result	Execution time	Memory
448182		blue	Wiring (IOI17_wiring)	C++17	30 / 100	1076 ms	18348 KiB

wiring

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


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);

    // cerr << "get score " << i << ' ' << p1 << ' ' << p2 << ' ' << ans << '\n';

    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()];

    // cerr << "blocks = " << X.size() << '\n';

    res[0] = vector<long long>(X[0].size());
    res[0][0] = 0;
    for(int j = 1; j < res[0].size(); j++)
    {
        // cerr << 0 << ' ' << j << ' ' << X[0][j] << ' ' << INF << '\n';
        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 << 1 << ' ' << j << ' ' << X[1][j] << ' ' << res[1][j] << '\n';
    }

    // cerr << "yes\n";

    for(int i = 2; i < X.size(); i++)
    {
        // cerr << "i = " << i << '\n';
        res[i] = vector<long long>(X[i].size());
        res[i][0] = res[i-1].back();
        // cerr << i << ' ' << 0 << ' ' << '?' << ' ' << res[i][0] << '\n';

        // 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);
        // }

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

            // cerr << i << ' ' << j << ' ' << X[i][j] << ' ' << res[i][j] << '\n';
        }
    }

    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:76: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]
   76 |     for(int i = 0; i < X.size(); i++)
      |                    ~~^~~~~~~~~~
wiring.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int j = 1; j < X[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~
wiring.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int j = 1; j < res[0].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
wiring.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int j = 1; j < res[1].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
wiring.cpp:113: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]
  113 |     for(int i = 2; i < X.size(); i++)
      |                    ~~^~~~~~~~~~
wiring.cpp:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for(int j = 1; j < res[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~
wiring.cpp:132:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for(int j1 = 1; j1 < res[i-1].size(); j1++)
      |                             ~~~^~~~~~~~~~~~~~~~~

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