oj.uz

Submission #589580

# Submission time Handle Problem Language Result Execution time Memory
589580 2022-07-04T21:43:06 Z TheScrasse Wiring (IOI17_wiring) C++17
13 / 100
 75 ms 11152 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 200010

long long min_total_length(vector<int> _r, vector<int> _b) {
    ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
    ll c1, c2, dp[maxn], bsl, bsm, bsu, ps[maxn];
    vector<array<ll, 2>> v;

    n = _r.size(); m = _b.size(); v.pb({-1, -1});
    for (i = 1; i <= n; i++) a[i] = _r[i - 1], v.pb({a[i], 0});
    for (i = 1; i <= m; i++) b[i] = _b[i - 1], v.pb({b[i], 1});

    sort(v.begin(), v.end());

    dp[0] = 0;
    for (i = 1; i <= n + m; i++) dp[i] = INF, ps[i] = ps[i - 1] + v[i][0];

    auto rs = [&](ll l, ll r) {
        return (ps[r] - ps[max((ll)0, l - 1)]);
    };

    auto calc = [&](ll bsm) {
        ll l1, r1, l2, r2, rr;
        l1 = bsm; r1 = c1 - 1; l2 = c1; r2 = i; rr = dp[max((ll)0, bsm - 1)];

        // cout << "calc" _ l1 _ r1 _ l2 _ r2 << nl;

        if (l1 > r1 || l2 > r2) return INF;
        rr -= rs(l1, r1); rr += rs(l2, r2);
        if (r1 - l1 > r2 - l2) rr += (((r1 - l1) - (r2 - l2)) * rs(l2, l2));
        else rr += (((r1 - l1) - (r2 - l2)) * rs(r1, r1));

        // cout << "rr =" _ rr << nl;
        rr = min(rr, INF);
        return rr;
    };

    auto good = [&](ll bsm) {
        return (calc(bsm) <= calc(bsm + 1));
    };

    c1 = 1; c2 = -1;
    for (i = 2; i <= n + m; i++) {
        if (v[i][1] != v[i - 1][1]) c2 = c1, c1 = i;
        if (c2 == -1) {
            continue;
        }

        bsl = c2 - 1; bsu = c1;
        // cout << "i, bsl, bsu =" _ i _ bsl _ bsu << nl;
        while (bsl != bsu) {
            bsm = (bsl + bsu) / 2;
            if (good(bsm)) bsu = bsm;
            else bsl = bsm + 1;
        }

        dp[i] = calc(bsl);
        // cout << "dp =" _ bsl _ dp[i] << nl;
    }

    /* for (i = 1; i <= n + m; i++) cout << dp[i] << ' ';
    cout << nl; */

	return dp[n + m];
}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:16:11: warning: unused variable 'i1' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |           ^~
wiring.cpp:16:15: warning: unused variable 'j' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |               ^
wiring.cpp:16:18: warning: unused variable 'k' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                  ^
wiring.cpp:16:21: warning: unused variable 'k1' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                     ^~
wiring.cpp:16:25: warning: unused variable 't' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                         ^
wiring.cpp:16:34: warning: unused variable 'res' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                                  ^~~
wiring.cpp:16:39: warning: unused variable 'flag' [-Wunused-variable]
   16 |     ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
      |                                       ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3432 KB Output is correct
2 Incorrect 2 ms 3372 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14522'
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3372 KB Output is correct
3 Correct 40 ms 10200 KB Output is correct
4 Correct 45 ms 10204 KB Output is correct
5 Correct 53 ms 10208 KB Output is correct
6 Correct 75 ms 11152 KB Output is correct
7 Correct 58 ms 11052 KB Output is correct
8 Correct 51 ms 11148 KB Output is correct
9 Correct 73 ms 11072 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3368 KB Output is correct
3 Incorrect 56 ms 11148 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1126115406'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 64 ms 10428 KB Output is correct
3 Correct 49 ms 10408 KB Output is correct
4 Correct 59 ms 10436 KB Output is correct
5 Correct 54 ms 10400 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Incorrect 3 ms 3376 KB 3rd lines differ - on the 1st token, expected: '25', found: '26'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3432 KB Output is correct
2 Incorrect 2 ms 3372 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14522'
3 Halted 0 ms 0 KB -