Submission #672559

#	Time	Username	Problem	Language	Result	Execution time	Memory
672559		mdub	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	588 ms	151368 KiB

shoes

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int power2(int n) {
  if (n == 0) return 1;
  else return 2*power2(n - 1);
}


int h;
vector<LL> tree;

void modify(int pos, LL inc) {
  pos += power2(h);
  tree[pos] += inc;
  while (pos != 1) {
    if (pos % 2) pos--;
    tree[pos/2] = tree[pos] + tree[pos + 1];
    pos /= 2;
  }
  //for (auto elem: tree) cout << elem << " ";
  //  cout << '\n';
}

LL query(int right) {
  int left = power2(h);
  right += power2(h);
  LL ret = 0;
  while (right != left) {
    if (right % 2 == 0) {
      ret += tree[right];
      right--;
    }
    right /= 2;
    left /= 2;
  }
  ret += tree[left];
  return ret;
}

LL count_swaps(vector<int> shoes) {
  int n = shoes.size();
  h = 1;
  while (power2(h) <= n + 1) h++;
  tree.assign(power2(h + 1), 0);
  for (int i = 0; i < n; i++) modify(i, 1);
  map<int, queue<int>> mp;
  for (int i = 0; i < n; i++) {
    mp[shoes[i]].push(i);
  }
  vector<bool> used(n, false);
  LL ans = 0;
  for (int i = 0; i < n; i++) {
    if (!used[i]) {
      used[i] = true;
      mp[shoes[i]].pop();
      queue<int>& cur = mp[0 - shoes[i]];
      ans += query(cur.front())-query(i)-1;
      //cout << query(cur.front()) << " " << query(i) <<" " << i << '\n';
      if (shoes[i] > 0) ans++;
      modify(cur.front(), -1);
      modify(i, +1);
      used[cur.front()] = true;
      
      cur.pop();
    }
  }
  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