Submission #1177300

#TimeUsernameProblemLanguageResultExecution timeMemory
1177300kunzaZa183Arranging Shoes (IOI19_shoes)C++20
100 / 100
528 ms156188 KiB
#include "shoes.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ti; long long count_swaps(vector<int> s) { map<int, queue<int>> mivi; for (int i = 0; i < s.size(); i++) { mivi[s[i]].push(i); ti.insert(i); } vector<int> taken(s.size(), 0); long long total = 0; for (int i = 0; i < s.size(); i++) { if (taken[i]) continue; // cout << i << " " << total << "\n"; ti.erase(ti.find_by_order(0)); mivi[s[i]].pop(); if (s[i] < 0) { // cout << i << " " << mivi[-s[i]].front() << '\n'; int x = ti.order_of_key(mivi[-s[i]].front()); total += x; taken[mivi[-s[i]].front()] = 1; ti.erase(mivi[-s[i]].front()); mivi[-s[i]].pop(); } else { // cout << i << " " << mivi[-s[i]].front() << '\n'; int x = ti.order_of_key(mivi[-s[i]].front()); total += x + 1; taken[mivi[-s[i]].front()] = 1; ti.erase(mivi[-s[i]].front()); mivi[-s[i]].pop(); } } return total; }
#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...