oj.uz

Submission #68775

# Submission time Handle Problem Language Result Execution time Memory
68775 2018-08-18T10:57:05 Z Inovak Wiring (IOI17_wiring) C++14
42 / 100
 127 ms 16136 KB 
//#include "grader.cpp"
#include "wiring.h"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define ll long long
#define OK puts("OK");
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 5e5+10;
const int nn = 2e5;
const ll inf = 1e16+7;

ll n, m, x, b;
ll dp[N], sum[N];
ll pr[N];
vector <pair <ll, ll> > all;

ll get(int l, int r) {
    return abs(sum[r] - sum[l - 1]);
}

long long min_total_length(vector<int> R, vector<int> B) {
    n = sz(R);
    m = sz(B);
    for(int i = 0; i < n; i++) {
        all.pb(mk(R[i], 1));
        dp[i+1] = inf;
    }
    for(int i = 0; i < m; i++) {
        all.pb(mk(B[i], 0));
        dp[i + n + 1] = inf;
    }

    if(R.back() < B[0]) {
        ll ans = 0;
        for(int i = 0; i < sz(R) - 1; i++)
            ans += R.back() - R[i];
        for(int i = 1; i < sz(B); i++)
            ans += B[i] - B[0];
        return ans + max(sz(R), sz(B)) * (B[0] - R.back());
    }

    R.insert(R.begin(), -inf);
    R.insert(R.end(), inf);
    B.insert(B.begin(), -inf);
    B.insert(B.end(), inf);

    n += m;
    all.pb(mk(-inf, -1));
    sort(all(all));
    memset(pr, -1, sizeof(pr));
    pr[nn] = 0;

    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + (all[i].sc ? -all[i].fr : all[i].fr);
        b += (all[i].sc ? -1 : 1);
        int j = pr[b + nn];
        pr[b + nn] = i;

        ll nl, nr;
        if (all[i].sc) {
            nl = *(lower_bound(B.begin(), B.end(), all[i].first) - 1);
            nr = *lower_bound(B.begin(), B.end(), all[i].first);
        }
        else {
            nl = *(lower_bound(R.begin(), R.end(), all[i].first) - 1);
            nr = *lower_bound(R.begin(), R.end(), all[i].first);
        }
        dp[i] = dp[i - 1] + min(all[i].first - nl, nr - all[i].first);

        if(j == -1) continue;
        dp[i] = min(dp[i], dp[j] + get(j + 1, i));
    }
    return dp[n];
}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:50:25: warning: overflow in implicit constant conversion [-Woverflow]
     R.insert(R.begin(), -inf);
                         ^~~~
wiring.cpp:51:26: warning: overflow in implicit constant conversion [-Woverflow]
     R.insert(R.end(), inf);
                          ^
wiring.cpp:52:25: warning: overflow in implicit constant conversion [-Woverflow]
     B.insert(B.begin(), -inf);
                         ^~~~
wiring.cpp:53:26: warning: overflow in implicit constant conversion [-Woverflow]
     B.insert(B.end(), inf);
                          ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4384 KB Output is correct
4 Correct 7 ms 4384 KB Output is correct
5 Correct 6 ms 4384 KB Output is correct
6 Correct 6 ms 4576 KB Output is correct
7 Correct 6 ms 4576 KB Output is correct
8 Correct 7 ms 4576 KB Output is correct
9 Correct 7 ms 4576 KB Output is correct
10 Correct 6 ms 4576 KB Output is correct
11 Correct 6 ms 4576 KB Output is correct
12 Correct 6 ms 4576 KB Output is correct
13 Correct 6 ms 4576 KB Output is correct
14 Correct 6 ms 4576 KB Output is correct
15 Correct 7 ms 4576 KB Output is correct
16 Correct 6 ms 4576 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4576 KB Output is correct
2 Correct 2 ms 4576 KB Output is correct
3 Correct 38 ms 8520 KB Output is correct
4 Incorrect 43 ms 9312 KB 3rd lines differ - on the 1st token, expected: '41599604178272', found: '41586719276384'
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9312 KB Output is correct
2 Correct 5 ms 9312 KB Output is correct
3 Correct 97 ms 16020 KB Output is correct
4 Correct 92 ms 16020 KB Output is correct
5 Correct 6 ms 16020 KB Output is correct
6 Correct 5 ms 16020 KB Output is correct
7 Correct 6 ms 16020 KB Output is correct
8 Correct 5 ms 16020 KB Output is correct
9 Correct 6 ms 16020 KB Output is correct
10 Correct 6 ms 16020 KB Output is correct
11 Correct 6 ms 16020 KB Output is correct
12 Correct 6 ms 16020 KB Output is correct
13 Correct 6 ms 16020 KB Output is correct
14 Correct 5 ms 16020 KB Output is correct
15 Correct 6 ms 16020 KB Output is correct
16 Correct 6 ms 16020 KB Output is correct
17 Correct 6 ms 16020 KB Output is correct
18 Correct 106 ms 16036 KB Output is correct
19 Correct 104 ms 16036 KB Output is correct
20 Correct 99 ms 16100 KB Output is correct
21 Correct 99 ms 16100 KB Output is correct
22 Correct 101 ms 16100 KB Output is correct
23 Correct 109 ms 16108 KB Output is correct
24 Correct 115 ms 16108 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16108 KB Output is correct
2 Correct 77 ms 16108 KB Output is correct
3 Correct 93 ms 16108 KB Output is correct
4 Correct 127 ms 16108 KB Output is correct
5 Correct 97 ms 16108 KB Output is correct
6 Correct 6 ms 16108 KB Output is correct
7 Correct 6 ms 16108 KB Output is correct
8 Correct 6 ms 16108 KB Output is correct
9 Correct 6 ms 16108 KB Output is correct
10 Correct 5 ms 16108 KB Output is correct
11 Correct 7 ms 16108 KB Output is correct
12 Correct 5 ms 16108 KB Output is correct
13 Correct 5 ms 16108 KB Output is correct
14 Correct 5 ms 16108 KB Output is correct
15 Correct 6 ms 16108 KB Output is correct
16 Correct 5 ms 16108 KB Output is correct
17 Correct 6 ms 16108 KB Output is correct
18 Correct 116 ms 16108 KB Output is correct
19 Correct 89 ms 16108 KB Output is correct
20 Correct 93 ms 16136 KB Output is correct
21 Correct 87 ms 16136 KB Output is correct
22 Correct 83 ms 16136 KB Output is correct
23 Correct 80 ms 16136 KB Output is correct
24 Correct 74 ms 16136 KB Output is correct

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4384 KB Output is correct
4 Correct 7 ms 4384 KB Output is correct
5 Correct 6 ms 4384 KB Output is correct
6 Correct 6 ms 4576 KB Output is correct
7 Correct 6 ms 4576 KB Output is correct
8 Correct 7 ms 4576 KB Output is correct
9 Correct 7 ms 4576 KB Output is correct
10 Correct 6 ms 4576 KB Output is correct
11 Correct 6 ms 4576 KB Output is correct
12 Correct 6 ms 4576 KB Output is correct
13 Correct 6 ms 4576 KB Output is correct
14 Correct 6 ms 4576 KB Output is correct
15 Correct 7 ms 4576 KB Output is correct
16 Correct 6 ms 4576 KB Output is correct
17 Correct 3 ms 4576 KB Output is correct
18 Correct 2 ms 4576 KB Output is correct
19 Correct 38 ms 8520 KB Output is correct
20 Incorrect 43 ms 9312 KB 3rd lines differ - on the 1st token, expected: '41599604178272', found: '41586719276384'
21 Halted 0 ms 0 KB -