제출 #361423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361423		spatarel	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1101 ms	71680 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];
bool active[2 * MAX_N];

void pair_up(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 {
      pair_up(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++) {
    active[i] = true;
  }
  for (int i = 0; i < 2 * n; i++) {
    if (active[i]) {
      for (int j = i + 1; j < pair[i]; j++) {
        if (active[j]) {
          answer++;
        }
      }
      if (s[i] > 0) {
        answer++;
      }
      active[i] = false;
      active[pair[i]] = false;
    }
  }
	return answer;
}

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