제출 #285745

#제출 시각아이디문제언어결과실행 시간메모리
285745williamMBDKArranging Shoes (IOI19_shoes)C++14
65 / 100
296 ms29036 KiB
#include<bits/stdc++.h> #define int long long #include "shoes.h" using namespace std; int N; struct BIT{ int N; vector<int> arr; BIT(int N){ this->N = N; arr = vector<int> (N); } int q(int idx){ int s = 0; while(idx > 0){ s += arr[idx]; idx -= (idx & (-idx)); } return s; } void u(int idx, int val){ while(idx < N){ arr[idx] += val; idx += (idx & (-idx)); } } }; int count_swaps_perm(vector<signed>& s, vector<int>& indices, vector<int>& perm) { BIT bit (N + 1); map<int,pair<int,vector<int>>> mp; for(int i = 0; i < N; i++){ mp[s[i]].second.push_back(i); bit.u(i + 1, i); if(i < N - 1) bit.u(i + 2, -i); } int res = 0; for(int i = 0; i < N / 2; i++){ int idx1 = indices[perm[i]]; res += bit.q(idx1 + 1); if(idx1 < N - 1) bit.u(idx1 + 2, -1); int idx2 = mp[s[idx1] * -1].second[mp[s[idx1] * -1].first++]; res += bit.q(idx2 + 1); if(idx2 < N - 1) bit.u(idx2 + 2,-1); } return res; } int rec(vector<signed>& s, vector<int>& indices, vector<int>& perm, vector<bool>& used, int idx){ if(idx == N / 2){ return count_swaps_perm(s, indices, perm); } int res = LLONG_MAX; for(int i = 0; i < N / 2; i++){ if(used[i]) continue; perm[idx] = i; used[i] = 1; res = min(res, rec(s, indices, perm, used, idx + 1)); used[i] = 0; perm[idx] = -1; } return res; } int count_swaps_brute(vector<signed> s, vector<int> indices){ vector<bool> used (N / 2); vector<int> perm (N / 2); return rec(s, indices, perm, used, 0); } int count_swaps_fast(vector<signed> s, vector<int> indices){ vector<int> temp (N / 2); for(int i = 0; i < N / 2; i++) temp[i] = i; return count_swaps_perm(s, indices, temp); } int count_swaps(vector<signed> s){ N = s.size(); vector<int> indices; for(int i = 0; i < N; i++){ if(s[i] < 0) indices.push_back(i); } if(N <= 16) return count_swaps_brute(s, indices); else return count_swaps_fast(s, indices); }
#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...