제출 #361424

#제출 시각아이디문제언어결과실행 시간메모리
361424spatarelArranging Shoes (IOI19_shoes)C++17
100 / 100
133 ms72428 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...