Submission #1061037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061037		vjudge1	Wiring (IOI17_wiring)	C++17	45 / 100	27 ms	2012 KiB

wiring

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

using namespace std;

typedef long long ll;

int get_closest(int x, vector<int> &vec){
    int lb = lower_bound(vec.begin(), vec.end(), x) - vec.begin();
    int res = 1e9 + 10;
    if (lb < vec.size())
        res = min(res, abs(x - vec[lb]));
    lb--;
    if (lb >= 0)
        res = min(res, abs(x - vec[lb]));
    return res;
}

ll min_total_length(vector<int> a, vector<int> b) {
    int n = a.size(), m = b.size();
    int p = 0, q = 0;

    if (n <= 1000 and m <= 1000){
        ll dp[n + 1][m + 1];
        memset(dp, 31, sizeof dp);
        dp[0][0] = 0;

        for (int i = 0; i <= n; i ++){
            for (int j = 0; j <= m; j ++){
                if (i == 0 and j == 0) continue;
                if (j != 0)
                    dp[i][j] = min(dp[i][j], dp[i][j - 1] + get_closest(b[j - 1], a));
                if (i != 0)
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + get_closest(a[i - 1], b));
                if (i != 0 and j != 0)
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(a[i - 1] - b[j - 1]));
            }
        }

        return dp[n][m];
    }

    ll ans = 0;
    while (p < n and q < m){
        int g1 = get_closest(a[p], b);
        int g2 = get_closest(b[q], a);

        if (g1 + g2 > abs(a[p] - b[q])){
            ans += abs(a[p] - b[q]);
            p++, q++;
            continue;
        }

        if (a[p] < b[q]){
            ans += g1;
            p++;
        }
        else{
            ans += g2;
            q++;
        }
    }

    while (p < n){
        ans += get_closest(a[p], b);
        p++;
    }

    while (q < m){
        ans += get_closest(b[q], a);
        q++;
    }

	return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'int get_closest(int, std::vector<int>&)':
wiring.cpp:11:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     if (lb < vec.size())
      |         ~~~^~~~~~~~~~~~

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