Submission #824424

#	Time	Username	Problem	Language	Result	Execution time	Memory
824424		erray	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	104 ms	139824 KiB

shoes

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

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/d1/debug.h"
#else 
  #define debug(...) void(37)
#endif


struct Fenwick {
  vector<int> sum;
  int n;
  Fenwick(int _n) : n(_n) {
    sum.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
      sum[i] = 1 << __builtin_ctz(i);
    }
  }
  void modify(int x) {
    x += 1;
    while (x <= n) {
      sum[x] -= 1;
      x += x & -x;
    }
  }
  int get(int x) {
    x += 1;
    int res = 0;
    while (x > 0) {
      res += sum[x];
      x -= x & -x;
    }
    return res;
  }
};

long long count_swaps(std::vector<int> S) {
  int N = int(S.size()) / 2;
  vector<queue<int>> g(2 * N + 1);
  vector<int> match(2 * N, -1);
  for (int i = 2 * N - 1; i >= 0; --i) {
    int need = -S[i] + N;
    if (g[need].empty()) {
      g[S[i] + N].push(i);
    } else {
      match[i] = g[need].front();
      g[need].pop();
    }
  }
  debug(match);
  Fenwick fenw(2 * N);
  long long ans = 0;
  for (int i = 0; i < 2 * N; ++i) {
    if (match[i] != -1) {
      fenw.modify(match[i]);
      fenw.modify(i);
      ans += fenw.get(match[i]) + (S[i] > 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