Submission #1149727

#TimeUsernameProblemLanguageResultExecution timeMemory
1149727kvintsekstakordArranging Shoes (IOI19_shoes)C++20
100 / 100
348 ms39556 KiB
#include "shoes.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using iset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; long long count_swaps(std::vector<int> s) { int n = s.size(); iset arr; map<int, set<int>> pos; for(int i = 0; i < n; i++){ arr.insert(i); pos[s[i]].insert(i); } long long ans = 0; while(!arr.empty()){ int beg = s[*arr.begin()]; int pairpos = *pos[-beg].begin(); int order = arr.order_of_key(pairpos); if(beg>0){ ans+=order; }else ans+=order-1; pos[-beg].erase(pairpos); pos[beg].erase(*arr.begin()); arr.erase(*arr.begin()); arr.erase(pairpos); } 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...