oj.uz

Submission #81154

# Submission time Handle Problem Language Result Execution time Memory
81154 2018-10-24T02:42:12 Z Hoansn Wiring (IOI17_wiring) C++14
0 / 100
 1000 ms 70100 KB 
#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]]);
    }
}

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 (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 (n > m) solve(0, n, m);
        else solve(1, m, n);
    cout << res;
}*/

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 67576 KB 3rd lines differ - on the 1st token, expected: '25859', found: '26187'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 67700 KB Output is correct
2 Correct 62 ms 67776 KB Output is correct
3 Execution timed out 1081 ms 70100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 70100 KB Output is correct
2 Incorrect 62 ms 70100 KB 3rd lines differ - on the 1st token, expected: '17703', found: '19704'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 70100 KB 3rd lines differ - on the 1st token, expected: '27', found: '32'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 67576 KB 3rd lines differ - on the 1st token, expected: '25859', found: '26187'
2 Halted 0 ms 0 KB -