Submission #1261065

#TimeUsernameProblemLanguageResultExecution timeMemory
1261065MegalosaurusArranging Shoes (IOI19_shoes)C++20
10 / 100
1 ms328 KiB
#include "shoes.h" // #include "grader.cpp" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include<bits/stdc++.h> using namespace __gnu_pbds; using namespace std; #define ordered_set 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(); map<int,vector<int>>mp; for(int i = 0; i < n; i++) { mp[s[i]].push_back(i); } ordered_set os; int ans = 0; for(int i = 0; i < n; i++) { if(os.find(i) != os.end()) continue; int sz = os.size(); int idx = upper_bound(mp[-s[i]].begin(), mp[-s[i]].end(), i)-mp[-s[i]].begin(); idx = mp[-s[i]][idx]; int a = sz-os.order_of_key(i), b = sz-os.order_of_key(idx); ans += idx-i-a+b-1; if(s[i] > 0) ans++; os.insert(idx); } 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...