Submission #155455

#	Time	Username	Problem	Language	Result	Execution time	Memory
155455		WLZ	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	230 ms	140000 KiB

shoes

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

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
 
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
 
  void modify(int x, T val) {
    for (; x < n; x += x & -x) {
      fenw[x] += val;
    }
  }
 
  T get(int x) {
    T ans{};
    for (; x > 0; x -= x & -x) {
      ans += fenw[x];
    }
    return ans;
  }
};

long long count_swaps(vector<int> s) {
  int n = (int) s.size() / 2, cur = 0;
  vector<int> a(2 * n);
  vector< queue<int> > q(2 * n + 1);
  for (int i = 0; i < 2 * n; i++) {
    if (q[n - s[i]].empty()) {
      q[n + s[i]].push(i);
      a[i] = 2 * cur;
      cur++;
    } else {
      int j = q[n - s[i]].front();
      q[n - s[i]].pop();
      a[i] = a[j] + 1;
      if (s[i] < 0) {
        swap(a[i], a[j]);
      }
    }
  }
  fenwick<int> fenw(2 * n + 2);
  long long ans = 0;
  for (int i = 0; i < 2 * n; i++) {
    ans += (long long) (i - fenw.get(a[i]));
    fenw.modify(a[i] + 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