제출 #987973

#제출 시각아이디문제언어결과실행 시간메모리
987973mannshah1211Arranging Shoes (IOI19_shoes)C++14
100 / 100
773 ms157012 KiB
/** * author: tourist * created: **/ #include "shoes.h" #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif template <typename T> class fenwick { public: vector<T> fenw; int n; fenwick(int _n) : n(_n) { fenw.resize(n); } void modify(int x, T v) { while (x < n) { fenw[x] += v; x |= (x + 1); } } T get(int x) { T v{}; while (x >= 0) { v += fenw[x]; x = (x & (x + 1)) - 1; } return v; } }; long long count_swaps(vector<int> a) { int n = a.size() / 2; long long swaps = 0; fenwick<int> fenw(2 * n); map<int, deque<int>> mp; for (int i = 0; i < 2 * n; i++) { mp[a[i]].push_back(i); } for (int i = 0; i < 2 * n; i++) { fenw.modify(i, 1); } set<int> unlock; for (int i = 0; i < 2 * n; i++) { unlock.insert(i); } for (int i = 0; i < 2 * n; i += 2) { int p = mp[-a[*unlock.begin()]].front(); swaps += fenw.get(p - 1) + (a[*unlock.begin()] > 0) - 1; fenw.modify(*unlock.begin(), -1); fenw.modify(p, -1); mp[a[*unlock.begin()]].pop_front(); mp[-a[*unlock.begin()]].pop_front(); unlock.erase(*unlock.begin()); unlock.erase(p); } return swaps; } // Version with comments: // Basically, always swap the leftmost shoe with whatever matches. // In order to simulate this process, we maintain a set of // unlocked positions (whose order never changes, till they get // paired with each other). And for the leftmost, we take // *unlocked.begin(). Also, you need the # of swaps, which reduce // to counting number of numbers < x (because there's nothing before // *unlocked.begin()), and add 1 when you need the extra swap. // Then, after each corrected pair, just update all your data structures.
#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...