Submission #868395

#TimeUsernameProblemLanguageResultExecution timeMemory
868395toma_ariciuArranging Shoes (IOI19_shoes)C++17
45 / 100
30 ms11476 KiB
#include "shoes.h" #include <algorithm> #include <iostream> 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), ord; vector <vector <int>> pos(n + 1, vector <int>()); int p1 = 0; for (int i = 0; i < 2 * n; i++) { if (s[i] < 0) { v[i] = p1; p1 += 2; ord.push_back(-s[i]); } } for (int i = 2 * n - 1; i >= 0; i--) { if (s[i] > 0) { int x = s[i]; pos[x].push_back(i); } } for (int i = 0; i < n; i++) { int x = ord[i]; int poz = pos[x].back(); pos[x].pop_back(); v[poz] = 2 * i + 1; } 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...