algorithms/coderun/0547.cpp at master · crystarm/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// https://coderun.yandex.ru/problem/linear-postman
// median + greedy + fast-sorting + big-input-optimization

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef unsigned long long ull;

typedef unsigned int u32_t;
typedef vector<u32_t> vu32_t;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    u32_t a, b;
    cin >> n;
    cin >> a >> b;

    u32_t cur = 0;

    auto nr24 = [&]() -> u32_t
    {
        cur = cur * a + b;
        return cur >> 8;
    };

    auto nr32 = [&]() -> u32_t
    {
        u32_t x = nr24();
        u32_t y = nr24();
        return (x << 8) ^ y;
    };

    vu32_t v(n), tmp(n);
    for (int i = 0; i < n; i++)
    {
        v[i] = nr32();
    }

    const int K = 1 << 16;
    static u32_t cnt[K];

    for (int pass = 0; pass < 2; pass++)
    {
        memset(cnt, 0, sizeof(cnt));
        int shift = pass * 16;

        for (u32_t x : v)
        {
            cnt[(x >> shift) & 0xFFFF]++;
        }

        u32_t sum = 0;
        for (int i = 0; i < K; i++)
        {
            u32_t c = cnt[i];
            cnt[i] = sum;
            sum += c;
        }

        for (u32_t x : v)
        {
            tmp[cnt[(x >> shift) & 0xFFFF]++] = x;
        }

        v.swap(tmp);
    }

    u32_t med = v[n / 2];

    ull ans = 0;
    for (u32_t x : v)
    {
        if (x >= med) ans += (ull)(x - med);
        else ans += (ull)(med - x);
    }

    cout << ans << "\n";
    return 0;
}