Submission #448227

#	Time	Username	Problem	Language	Result	Execution time	Memory
448227		blue	전선 연결 (IOI17_wiring)	C++17	30 / 100	1085 ms	67344 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;
}



struct segtree
{
    int l;
    int r;

    long long mn = 0;
    long long lp = 0;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;

        if(l == r) return;

        int m = (l+r)/2;

        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void add(int L, int R, long long V)
    {
        if(R < l || r < L) return;
        else if(L <= l && r <= R)
        {
            mn += V;
            lp += V;
        }
        else
        {
            left->add(L, R, V);
            right->add(L, R, V);

            mn = lp + min(left->mn, right->mn);
        }
    }

    long long rangemin(int L, int R)
    {
        if(R < l || r < L) return INF;
        else if(L <= l && r <= R) return mn;
        else return lp + min(left->rangemin(L, R), right->rangemin(L, R));
    }
};



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

        segtree S(0, res[i-1].size() + 5);


        for(int K = 1; K < res[i-1].size(); K++)
            S.add(K, K, min(res[i-1][K-1], res[i-1][K]));

        int prev_size = res[i-1].size();


        //j = 1
        for(int k = 1; prev_size - k >= 1; k++)
            S.add(prev_size - k, prev_size - k, k * (+1 * X[i][1]));

        for(int K = 1; K < res[i-1].size(); K++)
            S.add(K, K, -1 * (Xsum[i-1].back() - Xsum[i-1][K-1]));

        if(1 < res[i].size())
            res[i][1] = S.rangemin(1, res[i-1].size()-1);


        for(int j = 2; 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:134: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]
  134 |     for(int i = 0; i < X.size(); i++)
      |                    ~~^~~~~~~~~~
wiring.cpp:136:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for(int j = 1; j < X[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~
wiring.cpp:155:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int j = 1; j < res[0].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
wiring.cpp:163:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int j = 1; j < res[1].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
wiring.cpp:171: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]
  171 |     for(int i = 2; i < X.size(); i++)
      |                    ~~^~~~~~~~~~
wiring.cpp:181:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |         for(int K = 1; K < res[i-1].size(); K++)
      |                        ~~^~~~~~~~~~~~~~~~~
wiring.cpp:191:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for(int K = 1; K < res[i-1].size(); K++)
      |                        ~~^~~~~~~~~~~~~~~~~
wiring.cpp:198:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |         for(int j = 2; j < res[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~
wiring.cpp:201:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |             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