Submission #1313937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313937		voldi9	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1 ms	332 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#include <bit>
#include <unordered_map>

using namespace std;

void inline update(vector<int>& removed, int pos) {
  while (pos > 1)
    removed[pos>>=1]++;
}

int inline sum(vector<int>& removed, int i, int j) {
  int res = 0;
  while (i >> 1 < j >> 1) {
    if ((i % 2) == 0)
      res += removed[i+1];
    if ((j % 2) == 1)
      res += removed[j-1];
    i >>= 1;
    j >>= 1;
  } 
  return res;
}

int inline pwr(int x) {
  int res = 1;
  while (res < x) {
      res <<= 1;
  }
  return res;
}

long long count_swaps(std::vector<int> S) {
  long long res = 0;
  unordered_map<int, deque<int>> sizes[2];
  int N = pwr(S.size());
  vector<int> removed(2*N, 0);

  for (int i=0; i<S.size(); i++)
     S[i] < 0 ? sizes[0][-S[i]].push_back(i) : sizes[1][S[i]].push_back(i);

  for (int i=0; i<S.size(); i++) {
    if (sizes[0][abs(S[i])].empty() || sizes[S[i] > 0][abs(S[i])].front() > i)
      continue;
    int j = sizes[(S[i] < 0)][abs(S[i])].front();
    sizes[0][abs(S[i])].pop_front();
    sizes[1][abs(S[i])].pop_front();
    res += j - i - sum(removed, N+i, N+j);
    update(removed, N+j);
    if (S[i] < 0) res--;
  }
  return res;
}

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