Submission #418588

#TimeUsernameProblemLanguageResultExecution timeMemory
418588gromperenArranging Shoes (IOI19_shoes)C++17
0 / 100
2 ms2636 KiB
#include "shoes.h" #include <bits/stdc++.h> using ll = long long; using namespace std; const int MAXN = 1e5+5; int n; //vector<vector<pair<int,int>>> v(MAXN, vector<pair<int,int>>); struct fenwick { int tree[MAXN]; void update(int i, ll v) { for (; i <= n; i += (i & -1)) tree[i] += v; } ll query(int i) { ll s = 0; for (; i > 0; i -= (i & -i)) s += tree[i]; return s; } } fen; long long count_swaps(std::vector<int> s) { n = (int)s.size() / 2; ll ans = 0; vector<pair<int,int>>v; vector<pair<int,int>> ord[MAXN]; for (int i = 0; i < 2*n; ++i) { ord[abs(s[i])].emplace_back(s[i], i); } for (int i = 1; i <= n; ++i) { fen.update(i, -1); fen.update(i+n, -1); int m = ord[i].size(); for (int j = 0; j < m / 2; ++j) { int fi = ord[i][j].second; int se = ord[i][j + m/2].second; fi++; se++; if (fi > se) { // SHOES ARE LEFT & RIGHT SWAPPED swap(fi, se); ans++; } v.emplace_back(fi, se); } } sort(v.begin(),v.end()); int m = v.size(); for (int i = 0; i < m; ++i) { int f = v[i].first; int s = v[i].second; ans += fen.query(s-1) - fen.query(f); fen.update(f, -1); fen.update(s, -1); } return ans; }
#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...