Employment - 1214F

First, let's notice that the optimal answer can be achieved without changing the relative order of candidates. That means that if we order candidates by circle clockwise, the second candidate will work at the next clockwise workplace from the first candidate's workplace, the third candidate will work at the next clockwise workplace from the second candidate's workplace and so on. Let's prove it. If in optimal answer the order has changed, then there should be 2 candidates, so that the first of them lives earlier clockwise then the second and works at workplace, which is further. If we swap their workplaces, the distance between home and workplace for each of them will either stay the same or decrease. So, doing this swaps, we can achieve the situation, when the relative order of candidates stay the same.

Now we can come up with simple O(n2) solution. Let's first sort all candidates and workplaces by their city number. Let's select some workplace for the first candidate. Because in the optimal answer the order of candidates will not change, for each candidate we know his workplace. Now in O(n) time we can calculate the total distance. And because there are n possible workplaces for the first candidate, the solution works in O(n2) time.

To solve problem faster, let's notice, that if some candidate lives in city with number x and his workplace has number y, the the total distance from home to work for him will be:

−x+y+m if y<x−m/2
x−y if x−m/2≤y<x
−x+y if x≤y<x+m/2
x−y+m if x+m/2≤y
So for each candidate we have at most 4 intervals of workplaces positions, at which the sign before the candidate's home position in the distance formula stays the same. The same way for each workplace we have at most 4 intervals of candidates positions, where the sign before the workplace position in distance formula stays the same. Also, there are 4 intervals of candidates positions, where we need to add m to the distance formula. Because the relative order of candidates stays the same, we can iterate over all possible workplaces for the first candidate and check the total distance in each variant. When we move first candidate workplace to the next, for some candidates and workplaces their distance formula can change, but for each of them it can change no more then 4 times. So we will totally do no more then 8n changes. All in all we will check all distances in O(nlogn) time (we have additional logarithm because of sorting).

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using uint = unsigned int;
using db = long double;
using ii = pair<int,int>;
const int N =1e6+5, MOD = 1e9 + 7;
ll sum[N];
int ans[N], m, n;
void add(int l, int r, ll val){
  if(l <= r){
    sum[l] += val;
    sum[r+1] -= val;
  }
}
int32_t main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif

  cin >> m >> n;

  vector<pair<ll, ll>> a(n), b;

  for(int i = 0; i < n; i++){
    cin >> a[i].first;
    a[i].second = i + 1;
  }
  for(int i = 0, x; i < n; i++){
    cin >> x;
    b.push_back(make_pair(x,i + 1));
    b.push_back(make_pair(x-m,i + 1));
    b.push_back(make_pair(x+m,i + 1));
  }

  sort(b.begin(),b.end());
  sort(a.begin(), a.end());
  b.insert(b.begin(), make_pair(-1e16, 0));
  a.insert(a.begin(), make_pair(-1e16, 0));
  b.push_back(make_pair(1e16,0));
  a.push_back(make_pair(1e16,0));

  for(int i = 1; i <= n; i++){
    int j = upper_bound(b.begin(), b.end(), make_pair(a[i].first, LLONG_MAX)) - b.begin();
    int d = j - i;
        add(0, d - 1, a[i].first);

        add(d, 2 * n, -a[i].first);
  }
  for(int i = 1; i <= n+n+n; i++){
    int j = lower_bound(a.begin(), a.end(), make_pair(b[i].first, LLONG_MIN)) - a.begin() - 1;
    int d = i-j;
        add(max(0, i - n), min(d - 1, i - 1), -b[i].first);
        add(max(d, i - n), min(2 * n, i - 1), b[i].first);
  }

  ll mn = LLONG_MAX, cur = 0;
  int idx = -1;
  for(int i = 0; i <= n + n; i++){
    cur += sum[i];
    if(cur < mn){
      mn = cur;
      idx = i;
    }
  }

  cout << mn << '\n';
  for(int i = 1; i <= n; i++)
    ans[a[i].second] = b[i + idx].second;
  for(int i = 1; i <= n; i++)
    cout << ans[i] << " \n"[i==n];


  return 0;
}

#include <cstdio>
#include <algorithm>

using namespace std;

using ll = long long;
const int MN = 2e5 + 100;

int N, M;
ll F = 1e18, f;
ll p[MN*3];//equality = b-a
int g;
struct W
{
public:
    ll v; int i;
    void in(int i) {scanf("%lld", &v); W::i=i;}
    bool operator < (W o) const {return v < o.v;}
    bool operator < (ll x) const {return v < x;}
} A[MN], B[MN];
bool operator < (ll x, W y) {return x < y.v;}
int z[MN];

int main(void)
{
    scanf("%d%d", &M, &N);
    for(int i = 0;i < N;++i) A[i].in(i);
    for(int i = 0;i < N;++i) B[i].in(i);
    sort(A, A+N), sort(B, B+N);
    for(int i = 0;i < N;++i)
    {
        p[0] += M-A[i].v;
        p[i+1] -= M;
        p[i+N-(std::lower_bound(B, B+N, A[i].v)-B)+1] += A[i].v*2;
        p[i+N+1] += M;
    }
    for(int i = 0;i < N;++i)
        p[0] += B[i].v, p[N-i+(std::upper_bound(A, A+N, B[i].v)-A)]-=B[i].v*2;
    for(int i = 0;i <= N*2;++i)
        if((f+=p[i])<F)
            F=f, g=i;
    printf("%lld\n", F);
    for(int i = 0;i < N;++i)
        z[A[i].i] = B[(i+N*4-g)%N].i;
    for(int i = 0;i < N;i++)
        printf("%d%c", z[i]+1, " \n"[i==N-1]);
    return 0;
}


int m,n,ans[MX];
vpi a, b;

ll eval(int x) {
    ll ans = 0;
    F0R(i,n) ans += abs(a[x+i].f-b[i].f);
    return ans;
}

int main() {
    setIO(); re(m,n); a.rsz(n); b.rsz(n);
    F0R(i,n) {
        re(a[i].f);
        a[i].s = i+1;
    }
    F0R(i,n) {
        re(b[i].f);
        b[i].s = i+1;
    }
    sort(all(a));
    sort(all(b));
    a.rsz(3*n);
    F0R(i,3*n) {
        if (i < n) a[i].f -= m;
        else {
            a[i] = a[i-n];
            a[i].f += m;
        }
    }
    int lo = 0, hi = 2*n;
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (eval(mid) < eval(mid+1)) hi = mid;
        else lo = mid+1;
    }
    ps(eval(lo));
    F0R(i,n) ans[a[lo+i].s] = b[i].s;
    FOR(i,1,n+1) pr(ans[i],' ');
    /*F0R(i,2*n+1) ps(eval(i));
    ps(a,b);*/
}

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

using ll = long long;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll m;
    ll n;
    cin >> m >> n;
    vector<ll> _a(n);
    vector<ll> _b(n);
    vector<ll> a(n); vector<ll> b(n);
    map<ll, set<ll> > ax, bx;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i]--;
        a[i] *= 2;
        _a[i] = a[i];
        ax[_a[i]].insert(i);
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
        b[i]--;
        b[i] *= 2;
        _b[i] = b[i];
        bx[_b[i]].insert(i);
    }
    m *= 2;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector<pair<ll, ll> > events;
    for(int i = 0; i < n; i++){
        events.push_back({a[i], 0});
        events.push_back({b[i], 1});
        events.push_back({a[i]+m, 0});
        events.push_back({b[i]+m, 1});
    }
    sort(events.begin(), events.end());

    ll pos_sum = 0;
    ll neg_sum = 0;
    ll cur_ans = 0;

    map<ll, ll> freq;
    ll counter = 0;

    ll cpsum = 0;
    for(int i = 0; i < 2*n; i++){
        if(events[i].second == 0){
            cpsum += 1;
        } else {
            cpsum -= 1;
        }
        ll diff = events[i+1].first - events[i].first;
        freq[cpsum] += diff;
        if(cpsum > 0){
            pos_sum += diff;
        }
        if(cpsum < 0){
            neg_sum += diff;
        }
        cur_ans += abs(cpsum) * diff;
    }
    assert(cpsum == 0);
    ll ans = 2e18;
    ll ans_idx = -1;
    for(int i = 0; i < 2*n; i++){
        if(cur_ans < ans){
            ans = cur_ans;
            ans_idx = i;
        }
        if(events[i].second == 0){
            // subtract one from all
            neg_sum += freq[counter];
            cur_ans += neg_sum;
            counter += 1;
            cur_ans -= pos_sum;
            pos_sum -= freq[counter];
        } else {
            // add one from all
            pos_sum += freq[counter];
            cur_ans += pos_sum;
            counter -= 1;
            cur_ans -= neg_sum;
            neg_sum -= freq[counter];
        }
    }
    cout << ans / 2 << '\n';
    vector<ll> as, bs;
    for(ll _i = ans_idx; _i < ans_idx + 2*n; _i++){
        ll i = _i % (2 * n);
        if(events[i].second == 0){
            ll r = events[i].first % m;
            as.push_back(*ax[r].begin());
            ax[r].erase(ax[r].begin());
        } else {
            ll r = events[i].first % m;
            bs.push_back(*bx[r].begin());
            bx[r].erase(bx[r].begin());
        }
    }
    vector<ll> pp(n, -1);
    for(ll i = 0; i < n; i++){
        pp[as[i]] = bs[i];
    }
    for(ll i = 0; i < n; i++){
        cout << pp[i] + 1 << ' ';
    }
    cout << '\n';
}