제출 #971816

#제출 시각아이디문제언어결과실행 시간메모리
971816androArranging Shoes (IOI19_shoes)C++14
10 / 100
204 ms84400 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; const int N = 1e5 + 5; struct fenw { int t[N] = {0}; int query(int i) { int ans = 0; for(; i > 0; i -= i & - i) { ans += t[i]; } return ans; } void update(int i, int v) { for(; i < N; i += i & - i) { t[i] += v; } } }fenw; long long count_swaps(std::vector<int> s) { int n = s.size(); vector<int> a(n + 1); for(int i = 1; i <= n; i++) { a[i] = s[i - 1]; } map<int,int> M, M1; for(int i = 1; i <= n; i++) { if(a[i] > 0) { M[a[i]] += 1; } else { M1[a[i]] += 1; } } for(int i = 1; i <= n; i++) { if(a[i] > 0) { if(M[a[i]] != M1[-a[i]]) { return - 1; } } } map<int,set<int>> ms; for(int i = 1; i <= n; i++) { ms[a[i]].insert(i); } vector<int> izracunao(n + 1, 0); int ans = 0; for(int i = 1; i <= n; i++) { if(izracunao[i + fenw.query(i)]) { continue; } auto it = ms[-a[i]].upper_bound(i); if(it == ms[-a[i]].end()) { continue; } int idx = *it; idx += fenw.query(idx); if(a[i] > 0) { //cout << 1 << " " << i << " " << idx << "\n"; ans += (idx + fenw.query(idx)) - (i + fenw.query(i)); fenw.update(i, 1); fenw.update(idx, - 1); } else { //cout << 2 << " " << i << " " << idx << "\n"; ans += (idx + fenw.query(idx)) - (i + fenw.query(i)) - 1; fenw.update(i, 1); fenw.update(idx, - 1); } izracunao[idx + fenw.query(idx)] = 1; } return ans; } /* int main() { cout << count_swaps({2, 1, - 1, - 2}); }*/
#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...