Submission #772220

#	Time	Username	Problem	Language	Result	Execution time	Memory
772220		Olympia	Simfonija (COCI19_simfonija)	C++17	110 / 110	136 ms	6348 KiB

simfonija

#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <climits>
#include <map>
typedef long long ll;
using namespace std;
const int MIN = - (ll)2e6 - 10;
const int MAX = (ll)2e6 + 10;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    map<ll,int> oc;
    ll neg_sum = 0, neg_num = n, pos_num = 0, pos_sum = 0;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        a[i] -= x;
        oc[a[i]]++;
        neg_sum += abs(a[i] + MIN);
    }
    sort(a.begin(), a.end());
    ll res = LLONG_MAX;
    int l = k - 1; //0 to l
    int r = n; //r to n - 1
    ll sum_left = 0, sum_right = 0;
    for (int i = 0; i <= l; i++) {
        sum_left += -a[i] - MIN;
    }
    //cout << a[k] << " " << a.back()
    for (ll x = MIN + 1; x <= MAX; x++) { //go from neg to pos
        while (l != -1 and r - 1 < a.size() and -a[l] - x < abs(a[r - 1] + x)) {
            sum_left += x - 1 + a[l];
            sum_right += abs(x - 1 + a[r - 1]);
            l--, r--;
        }
        sum_left -= l + 1;
        sum_right += n - r;
        if (oc.count(- x + 1)) { //this will go from 0 to 1
            pos_num += oc[-x + 1];
            neg_num -= oc[-x + 1];
        }
        assert(sum_left >= 0 and sum_right >= 0 and pos_sum >= 0 and neg_sum >= 0);
        pos_sum += pos_num;
        neg_sum -= neg_num;
        res = min(res, pos_sum + neg_sum - sum_left - sum_right);
    }
    cout << res << '\n';
}

Compilation message (stderr)

simfonija.cpp: In function 'int main()':
simfonija.cpp:44:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while (l != -1 and r - 1 < a.size() and -a[l] - x < abs(a[r - 1] + x)) {
      |                            ~~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11