제출 #307911

#제출 시각아이디문제언어결과실행 시간메모리
307911mihai145Arranging Shoes (IOI19_shoes)C++14
100 / 100
262 ms25212 KiB
#include "shoes.h" #include <vector> #include <set> const int NMAX = 1e5; int N; int shoes[2 * NMAX + 2]; std::vector<int> l[NMAX + 2], r[NMAX + 2]; std::set<int> pos; int aib[2 * NMAX + 2]; inline int LSB(int x) { return x & -x; } void Update(int pos, int val) { for(int i = pos; i <= N; i += LSB(i)) aib[i] += val; } int Query(int pos) { int ans = 0; for(int i = pos; i > 0; i -= LSB(i)) ans += aib[i]; return ans; } long long count_swaps(std::vector<int> s) { N = (int)s.size(); for(int i = 0; i < N; i++) { shoes[i + 1] = s[i]; if(shoes[i + 1] < 0) l[-shoes[i + 1]].push_back(i + 1); else r[shoes[i + 1]].push_back(i + 1); pos.insert(i + 1); } for(int i = 1; i <= N; i++) Update(i, 1); long long swaps = 0LL; for(int i = 1; i <= N / 2; i++) { int p = *pos.rbegin(); if(shoes[p] > 0) { ///rightShoo swaps += 1LL * (Query(N) - Query(l[shoes[p]].back()) - 1); pos.erase(p); pos.erase(l[shoes[p]].back()); Update(p, -1); Update(l[shoes[p]].back(), -1); l[shoes[p]].pop_back(); r[shoes[p]].pop_back(); } else { ///leftShoo swaps += 1LL * (Query(N) - Query(r[-shoes[p]].back())); pos.erase(p); pos.erase(r[-shoes[p]].back()); Update(p, -1); Update(r[-shoes[p]].back(), -1); l[-shoes[p]].pop_back(); r[-shoes[p]].pop_back(); } } return swaps; }
#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...