Submission #146604

#	Time	Username	Problem	Language	Result	Execution time	Memory
146604		AlexPop28	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	118 ms	20412 KiB

shoes

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

using namespace std;

struct Fenwick {
  int n;
  vector<int> tree;
  Fenwick(int n_) : n(n_), tree(n + 1) {}
  inline int lsb(int x) {
    return x & -x;
  }
  void Update(int pos, int val) {
    for (++pos; pos <= n; pos += lsb(pos))
      tree[pos] += val;
  }
  int Query(int pos) {
    int ret = 0;
    for (++pos; pos >= 1; pos -= lsb(pos))
      ret += tree[pos];
    return ret;
  }
};

long long count_swaps(vector<int> s) {
  int n = s.size();
  vector<vector<int>> left(n + 1), right(n + 1);
  for (int i = 0; i < n; ++i) {
    if (s[i] < 0) left[-s[i]].emplace_back(i);
    else right[s[i]].emplace_back(i);
  }
  vector<pair<int, int>> pairs; pairs.reserve(n);
  for (int size = 1; size <= n / 2; ++size) {
    assert(left[size].size() == right[size].size());
    for (int j = 0; j < (int)left[size].size(); ++j) {
      pairs.emplace_back(left[size][j], right[size][j]);
    }
  }
  sort(pairs.begin(), pairs.end(), [](const pair<int, int> &a, const pair<int, int> &b){
    return a.first + a.second < b.first + b.second;
  });
  Fenwick tree(n);
  long long idx = 0, ans = 0LL;
  for (auto &p : pairs) {
    int l, r; tie(l, r) = p;
    l += tree.Query(l);
    r += tree.Query(r);
    //~ cerr << l << ' ' << r << endl;
    ans += l - idx + r - idx - 1;
    if (l > r) ++ans;
    tree.Update(0, 2);
    tree.Update(p.first, -1);
    tree.Update(p.second, -1);
    idx += 2;
  }
  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