Submission #550568

#	Time	Username	Problem	Language	Result	Execution time	Memory
550568		hoanghq2004	Wiring (IOI17_wiring)	C++14	13 / 100	41 ms	7484 KiB

wiring

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "wiring.h"

using namespace __gnu_pbds;
using namespace std;

const int N = 1e5 + 10;

struct Point {
    int x, red;
    int operator < (const Point& other) const {
        return x < other.x;
    }
};


vector <Point> A;
long long f[N], g[N];

long long min_total_length(vector <int> r, vector <int> b) {
    for (auto x: r) A.push_back({x, 1});
    for (auto x: b) A.push_back({x, 0});
    sort(A.begin(), A.end());
    vector <vector <Point> > s;
    for (int i = 0; i < A.size(); ) {
        int j = i;
        vector <Point> cur;
        while (j < A.size() && A[i].red == A[j].red) cur.push_back(A[j]), ++j;
        i = j;
        s.push_back(cur);
    }
/*
4 5
1 2 3 7
0 4 5 9 10

3 1
1 2 3
0
*/
    memset(f, 60, sizeof(f));
    memset(g, 60, sizeof(g));
    f[0] = 0;
    for (int id = 0; id < s.size(); ++id) {
        auto A = s[id];
        long long cur = 0;
        for (int i = 0; i < A.size(); ++i) {
            g[i] = f[i] + cur;
            cur += A[i].x - A[0].x;
        }
        g[A.size()] = f[A.size()] + cur;
        if (id) {
            for (int i = A.size() - 1; i >= 0; --i)
                g[i] = min(g[i], g[i + 1]);
//            for (int i = 0; i < A.size(); ++i) g[i] = min(g[i], f[i]);
        }
        if (id + 1 == s.size()) break;
        cur = 0;
        for (int i = 0; i < s[id].size(); ++i) {
            f[i] = g[s[id].size() - i] + cur;
            if (i) f[i] = min(f[i], f[i - 1] + s[id + 1][0].x - A.back().x);
            cur += s[id + 1][0].x - A[s[id].size() - i - 1].x;
        }
        f[s[id].size()] = g[0] + cur;
        for (int i = s[id].size() + 1; i <= s[id + 1].size(); ++i)
            f[i] = f[i - 1] + s[id + 1][0].x - A.back().x;
        for (int i = max(s[id].size(), s[id + 1].size()); i >= 1; --i)
            f[i - 1] = min(f[i - 1], f[i]);
    }
    return g[s.back().size()];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < A.size(); ) {
      |                     ~~^~~~~~~~~~
wiring.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         while (j < A.size() && A[i].red == A[j].red) cur.push_back(A[j]), ++j;
      |                ~~^~~~~~~~~~
wiring.cpp:48:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Point> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int id = 0; id < s.size(); ++id) {
      |                      ~~~^~~~~~~~~~
wiring.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < A.size(); ++i) {
      |                         ~~^~~~~~~~~~
wiring.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Point> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if (id + 1 == s.size()) break;
      |             ~~~~~~~^~~~~~~~~~~
wiring.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0; i < s[id].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
wiring.cpp:69:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i = s[id].size() + 1; i <= s[id + 1].size(); ++i)
      |                                        ~~^~~~~~~~~~~~~~~~~~~

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