Submission #868398

#TimeUsernameProblemLanguageResultExecution timeMemory
868398toma_ariciuArranging Shoes (IOI19_shoes)C++17
100 / 100
113 ms140628 KiB
#include "shoes.h" #include <algorithm> #include <iostream> #include <queue> using namespace std; class FenwickTree { private: int sz; vector <int> v; int lsb(int x) { return (x & (-x)); } public: FenwickTree(int n) { sz = n; v.resize(sz + 1); } void update(int poz) { for (int i = poz; i <= sz; i += lsb(i)) { v[i]++; } } int query(int poz) { int ans = 0; for (int i = poz; i; i -= lsb(i)) { ans += v[i]; } return ans; } }; int n; long long computeInversions(vector <int> v) { long long inv = 0; FenwickTree aib(2 * n); for (int i = 2 * n - 1; i >= 0; i--) { inv += aib.query(v[i]); aib.update(v[i] + 1); } return inv; } long long count_swaps(vector<int> s) { n = (int) s.size() / 2; vector <int> v(2 * n); vector <queue <int>> q(2 * n + 1); int p = 0; for (int i = 0; i < 2 * n; i++) { if (s[i] > 0) { if (!q[n + s[i]].empty()) { int poz = q[n + s[i]].front(); q[n + s[i]].pop(); v[poz] = p; v[i] = p + 1; p += 2; } else { q[s[i]].push(i); } } else { if (!q[-s[i]].empty()) { int poz = q[-s[i]].front(); q[-s[i]].pop(); v[poz] = p + 1; v[i] = p; p += 2; } else { q[n - s[i]].push(i); } } } return computeInversions(v); }
#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...