Submission #361424

#	Time	Username	Problem	Language	Result	Execution time	Memory
361424		spatarel	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	133 ms	72428 KiB

shoes

#include "shoes.h"
#include <math.h>
#include <stdio.h>
#include <queue>

const int MAX_N = 100000;

std::queue<int> indexes[1 + MAX_N];
int pair[2 * MAX_N];

int BIT[1 + 2 * MAX_N];

void addValue(int index, int addValue) {
  index++;
  for (int i = index; i <= 2 * MAX_N; i += i&-i) {
    BIT[i] += addValue;
  }
  //printf("addValue(%d, %d)\n", index - 1, addValue);
}

int prefixSum(int index) {
  index++;
  int answer = 0;
  for (int i = index; i > 0; i -= i&-i) {
    answer += BIT[i];
  }
  //printf("prefixSum(%d) -> %d\n", index - 1, answer);
  return answer;
}

void pairUp(int i, int j) {
  pair[i] = j;
  pair[j] = i;
}

long long count_swaps(std::vector<int> s) {
  int n = (int)s.size() / 2;
  for (int i = 0; i < 2 * n; i++) {
    int value = abs(s[i]);
    if (indexes[value].empty() || s[indexes[value].front()] == s[i]) {
      indexes[value].push(i);
    } else {
      pairUp(i, indexes[value].front());
      indexes[value].pop();
    }
  }
  /*
  printf("%d: ", n);
  for (int i = 0; i < 2 * n; i++) {
    printf("%d ", pair[i]);
  }
  printf("\n");//*/
  long long answer = 0;
  for (int i = 0; i < 2 * n; i++) {
    addValue(i, +1);
  }
  for (int i = 0; i < 2 * n; i++) {
    if (i < pair[i]) {
      addValue(i, -1);
      addValue(pair[i], -1);
      answer += prefixSum(pair[i]);
      if (s[i] > 0) {
        answer++;
      }
    }
    //printf("%lld ", answer);
  }
	return answer;
}

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