Submission #311776

#	Time	Username	Problem	Language	Result	Execution time	Memory
311776		MilosMilutinovic	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	298 ms	275464 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

const int N = 2e5 + 5;

vector<int> fenw(N, 0);
queue<int> l[N], r[N];

void Add(int x, int val) {
  for (; x < N; x += x & -x) {
    fenw[x] += val;
  }
}

long long Get(int x) {
  long long res = 0;
  for (; x > 0; x -= x & -x) {
    res += fenw[x];
  }
  return res;
}

bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.first + a.second - (a.first > a.second) > b.first + b.second - (b.first > b.second);
}

long long count_swaps(vector<int> a) {
  int n = (int) a.size();
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
      l[a[i]].push(i);
    } else {
      r[-a[i]].push(i);
    }
  }
  vector<pair<int, int>> v;
  for (int i = 1; i <= n / 2; i++) {
    while (!l[i].empty()) {
      v.push_back({l[i].front(), r[i].front()});
      l[i].pop();
      r[i].pop();
    }
  }
  sort(v.begin(), v.end(), cmp);
  for (int i = 0; i < n; i += 2) {
    auto k = v.back();
    v.pop_back();
    ans += k.first + k.second - (k.first > k.second) + Get(n) * 2 - Get(k.first + 1) - Get(k.second + 1) - i * 2;
    Add(k.first + 1, 1);
    Add(k.second + 1, 1);
  }
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15