제출 #987966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987966		mannshah1211	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	734 ms	157696 KiB

shoes

/**
 *    author: tourist
 *    created:
**/
#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <typename T>
class fenwick {
 public:
  vector<T> fenw;
  int n;

  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }

  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }

  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

long long count_swaps(vector<int> a) {
  int n = a.size() / 2;
  long long swaps = 0;
  fenwick<int> fenw(2 * n);
  map<int, deque<int>> mp;
  for (int i = 0; i < 2 * n; i++) {
    mp[a[i]].push_back(i);
  }
  for (int i = 0; i < 2 * n; i++) {
    fenw.modify(i, 1);
  }
  set<int> unlock;
  for (int i = 0; i < 2 * n; i++) {
    unlock.insert(i);
  }
  for (int i = 0; i < 2 * n; i += 2) {
    int p = mp[-a[*unlock.begin()]].front();
    swaps += fenw.get(p - 1) + (a[*unlock.begin()] > 0) - 1;
    fenw.modify(*unlock.begin(), -1);
    fenw.modify(p, -1);
    mp[a[*unlock.begin()]].pop_front();
    mp[-a[*unlock.begin()]].pop_front();
    unlock.erase(*unlock.begin());
    unlock.erase(p);
  }
  return swaps;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15