제출 #170618

#제출 시각아이디문제언어결과실행 시간메모리
170618nobikArranging Shoes (IOI19_shoes)C++14
100 / 100
753 ms148188 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; struct FenwichTree { int n; vector<int> f; FenwichTree(int n): n(n), f(n + 1) {} void Modify(int pos, int value) { for (int i = pos + 1; i <= n; i += i & -i) { f[i] += value; } } int Get(int pos) { int result = 0; for (int i = pos + 1; i > 0; i -= i & -i) { result += f[i]; } return result; } }; vector<int> GetShoePairs(const vector<int>& s) { int n = static_cast<int>(s.size()); vector<int> shoe_pair(n); map<int, queue<int>> position; for (int i = 0; i < n; ++i) { int shoe = s[i]; if (!position[-shoe].empty()) { int pos = position[-shoe].front(); shoe_pair[pos] = i; shoe_pair[i] = pos; position[-shoe].pop(); continue; } position[shoe].push(i); } return shoe_pair; } long long count_swaps(std::vector<int> s) { int n = static_cast<int>(s.size()); vector<int> shoe_pair = GetShoePairs(s); vector<int> used(n); FenwichTree tree(n); for (int i = 0; i < n; ++i) tree.Modify(i, +1); long long result = 0; for (int i = 0; i < n; ++i) { if (used[i]) continue; int pr = shoe_pair[i]; int actual_pos = tree.Get(pr) - 1; if (s[i] < 0) result += actual_pos - 1; else result += actual_pos; used[i] = used[pr] = 1; tree.Modify(i, -1); tree.Modify(pr, -1); } return result; }
#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...