Submission #81170

#	Time	Username	Problem	Language	Result	Execution time	Memory
81170		Hoansn	Wiring (IOI17_wiring)	C++14	0 / 100	90 ms	69588 KiB

wiring

#include <bits/stdc++.h>

#define fi first
#define se second
#define maxn 100007
#define fuck cerr << "Fuck" << '\n';
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;

const int oo = 1e5 + 7;;

int n, m, a[2][maxn];
ll res = 0;
deque <int> f[maxn];

void solve(int id, int n, int m) {
    for (int i = 1; i <= n; i++) {
        int t = lower_bound(a[!id] + 1, a[!id] + m + 1, a[id][i]) - a[!id];
        if (abs(a[id][i] - a[!id][t]) <= abs(a[id][i] - a[!id][t-1])) {
            f[t].push_back(i);
        }
        else f[t-1].push_back(i);
    }
    for (int i = 1; i<=m; i++) {
        if (f[i].size()) continue;
        int t = i-1;
        while (true) {
            if (t == 0 || f[t].size() > 1) break;
            t--;
        }
        int t2 = i+1;
        while (true) {
            if (t2 == m+1 || f[t2].size() > 1) break;
            t2++;
        }
        int t1;
        if (t == 0) t1 = -oo;
            else t1 = a[id][f[t].back()];
        int t3;
        if (t2 == m+1) t3 = -oo;
            else t3 = a[id][f[t2].front()];
        if (abs(a[!id][i] - t1) <= abs(a[!id][i] - t3)) {
            int tmp = f[t].back();
            f[i].push_back(tmp);
            f[t].pop_back();
        }
        else {
            int tmp = f[t2].front();
            f[i].push_back(tmp);
            f[t2].pop_front();
        }
    }
    for (int i = 1; i<=m; i++) {
        for (int j = 0; j<f[i].size(); j++)
            res += abs(a[!id][i] - a[id][f[i][j]]);
    }
}

void fuck_solve() {
    if (n == m) {
        for (int i = 1; i<=n; i++) res -= a[0][i];
        for (int i = 1; i<=m; i++) res += a[1][i];
    }
    if (n > m) {
        for (int i = 1; i<=n; i++) res -= a[0][i];
        for (int i = 1; i<=m; i++) res += a[1][i];
        res += a[1][1] * (n - m);
    }
    if (n < m) {
        for (int i = 1; i<=n; i++) res -= a[0][i];
        for (int i = 1; i<=m; i++) res += a[1][i];
        res -= a[0][n] * (m - n);
    }
}

ll min_total_length(vector <int> r, vector <int> b) {
    n = r.size();
    m = b.size();
    a[0][0] = -oo;
    a[1][0] = -oo;
    a[0][n+1] = -oo;
    a[1][m+1] = -oo;
    for (int i = 1; i<=n; i++) a[0][i] = r[i-1]; //cin >> a[0][i];
    for (int i = 1; i<=m; i++) a[1][i] = b[i-1]; //cin >> a[1][i];
    if (a[0][n] <= a[1][1]) {
        fuck_solve();
    }
    else {
        if (n > m) solve(0, n, m);
            else solve(1, m, n);
    }
    return res;
}


/*int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("wiring.inp", "r", stdin);
    //freopen("wiring.out", "w", stdout);
    cin >> n >> m;
    a[0][0] = -oo;
    a[1][0] = -oo;
    a[0][n+1] = -oo;
    a[1][m+1] = -oo;
    for (int i = 1; i<=n; i++) cin >> a[0][i];
    for (int i = 1; i<=m; i++) cin >> a[1][i];
    if (a[0][n] <= a[1][1]) {
        fuck_solve();
    }
    else {
        if (n > m) solve(0, n, m);
            else solve(1, m, n);
    }
    cout << res;
}*/

Compilation message (stderr)

wiring.cpp: In function 'void solve(int, int, int)':
wiring.cpp:55:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j<f[i].size(); j++)
                         ~^~~~~~~~~~~~

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