제출 #699943

#제출 시각아이디문제언어결과실행 시간메모리
699943elkernosArranging Shoes (IOI19_shoes)C++17
100 / 100
309 ms407116 KiB
#include "shoes.h" #include "bits/stdc++.h" using namespace std; #define ssize(x) (int)size(x) template <class A, class B> auto &operator<<(ostream &o, pair<A, B> p) { return o << '(' << p.first << ", " << p.second << ')'; } template <class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) { o << '{'; int i = 0; for (auto e : x) o << (", ") + 2 * !i++ << e; return o << '}'; } #ifdef DEBUG #define debug(x...) cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x), cerr << '\n' #else #define debug(...) \ { \ } #endif long long count_swaps(vector<int> s) { int n = ssize(s); vector<vector<deque<int>>> pos(2, vector<deque<int>>(n + 1)); vector<int> pary(n); vector<int> order; for (int i = 0; i < n; i++) { int rozm = abs(s[i]), sign = s[i] > 0; if (ssize(pos[sign ^ 1][rozm])) { int kto = pos[sign ^ 1][rozm].front(); pos[sign ^ 1][rozm].pop_front(); pary[kto] = i; } else { pos[sign][rozm].push_back(i); order.push_back(i); } } debug(pary, order); vector<int> fen(n + 1); auto pisz = [&](int x) { for (x++; x; x -= x & -x) fen[x]++; }; auto ile = [&](int x) { int ans = 0; for (x++; x <= n; x += x & -x) ans += fen[x]; return ans; }; long long ans = 0; for (int x : order) { int lo = x + ile(x); int hi = pary[x] + ile(pary[x]); ans += hi - lo - 1 + (s[x] > 0); debug(ans); pisz(pary[x]); } 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...