Submission #757765

#	Time	Username	Problem	Language	Result	Execution time	Memory
757765		taher	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	646 ms	148832 KiB

shoes

#include <bits/stdc++.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 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> v){
  int n = (int)v.size();
  map<int , deque<int>> Mp;
  for(int i = 0 ; i < n ; i++){
    Mp[v[i]].emplace_back(i);
  }
  fenwick<long long> q(n + 1);
  long long ans = 0;
  int coun = 1;
  int cnt = 0;
  for(int i = 0 ; i < n ; i++){
    int cur = v[i];
    if(Mp[cur].front() != i) continue;
    if(cur < 0){
      cnt++;
    }
    int f = cur * -1;
    assert(f != cur);
    int idx = Mp[f].front();
    Mp[cur].pop_front();
    Mp[f].pop_front();
    int now_f = q.get(idx);
    if(now_f + idx > cnt){
      int g_idx = now_f + idx;
      ans += (g_idx - cnt);
      q.modify(idx + 1, -1);
      q.modify(0 , 1);      
    }    
    cnt = coun * 2;
    coun++;
  }
  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