제출 #613991

#제출 시각아이디문제언어결과실행 시간메모리
613991AlperenTArranging Shoes (IOI19_shoes)C++17
50 / 100
1080 ms46976 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; const int N = 2e5 + 5; int n; struct Fenwick{ int tree[N]; int getsum(int r){ int sum = 0; for(int i = r; i > 0; i -= i & -i) sum += tree[i]; return sum; } int query(int l, int r){ return getsum(r) - getsum(l - 1); } void update(int pos, int val){ for(int i = pos; i < N; i += i & -i) tree[i] += val; } }; Fenwick fw; int findcnt(vector<int> a, vector<int> b){ map<int, vector<int>> nums; for(int i = 0; i < n; i++) nums[b[i]].push_back(i + 1); for(int i = 0; i < n; i++){ int x = *nums[a[i]].begin(); nums[a[i]].erase(nums[a[i]].begin()); a[i] = x; } long long inv = 0; for(auto x : a){ inv += fw.query(x + 1, N - 1); fw.update(x, 1); } return inv; } long long count_swaps(vector<int> arr){ n = arr.size(); vector<bool> flag(n, false); map<int, vector<int>> mp; for(int i = 0; i < n; i++){ if(mp[-arr[i]].empty()) mp[arr[i]].push_back(i); else{ flag[*mp[-arr[i]].begin()] = true; mp[-arr[i]].erase(mp[-arr[i]].begin()); } } vector<int> bestarr; for(int i = 0; i < n; i++){ if(flag[i]){ bestarr.push_back(-abs(arr[i])); bestarr.push_back(abs(arr[i])); } } return findcnt(arr, bestarr); }
#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...