Submission #263210

#	Time	Username	Problem	Language	Result	Execution time	Memory
263210		Bruteforceman	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	680 ms	148216 KiB

shoes

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

long long count_swaps(std::vector<int> v) {
  int n = v.size();
  vector <int> t (n + 1, 0);
  auto update = [&] (int x, int val) {
    for(int i = x; i <= n; i += i & (-i)) {
      t[i] += val;
    }
  };
  auto query = [&] (int x) {
    long long sum = 0;
    for(int i = x; i > 0; i -= i & (-i)) {
      sum += t[i];
    }
    return sum;
  };
  map <int, queue <int>> pos;
  for(int i = 1; i <= n; i++) {
    pos[v[i - 1]].push(i);
    update(i, 1);
  }
  long long ans = 0;
  for(int i = 1; i <= n; i++) {
    if(v[i - 1] == 0) continue;
    int idx = pos[-v[i - 1]].front();
    pos[-v[i - 1]].pop();
    pos[v[i - 1]].pop();
    update(i, -1);
    update(idx, -1);
    ans += query(idx);
    if(v[i - 1] > 0) ++ans;
    v[i - 1] = v[idx - 1] = 0;
  }
	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