Submission #1268836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268836		FaresSTH	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 KiB

shoes

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

static inline long long floordiv2(long long x){  // floor(x/2) for negative x too
    return (x>=0) ? (x/2) : -(( -x + 1 )/2);
}

// Return -1 if impossible (not enough even slots)
ll count_swaps(const vector<int>& a){
    int n = (int)a.size();
    vector<int> neg;
    neg.reserve(n);
    for (int i=0;i<n;i++) if (a[i] < 0) neg.push_back(i);

    int m = (int)neg.size();
    int E = (n + 1) / 2;                 // number of even indices: 0,2,4,...
    if (m > E) return -1;                // impossible: not enough even slots

    // v_k = neg[k] - 2*k
    vector<long long> v(m);
    for (int k=0;k<m;k++) v[k] = (long long)neg[k] - 2LL*k;

    // median of v (average O(n) with nth_element)
    long long M;
    if (m == 0) return 0;
    nth_element(v.begin(), v.begin()+m/2, v.end());
    M = v[m/2];

    auto clamp = [&](long long s){
        long long lo = 0, hi = (long long)E - m;
        if (s < lo) s = lo;
        if (s > hi) s = hi;
        return s;
    };

    auto cost = [&](long long s){
        long long sum = 0;
        for (int k=0;k<m;k++) sum += llabs( (long long)neg[k] - 2LL*(k + s) );
        return sum;
    };

    // 2*s should be near M; check both floor/ceil (and clamped)
    long long sA = clamp( floordiv2(M) );
    long long sB = clamp( floordiv2(M + 1) );

    return min(cost(sA), cost(sB));
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccp5WlFM.o: in function `main':
grader.cpp:(.text.startup+0x26b): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status