Submission #775553

#TimeUsernameProblemLanguageResultExecution timeMemory
7755531binArranging Shoes (IOI19_shoes)C++14
50 / 100
283 ms364660 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int b = 1 << 17; int n, seg[b * 2], li, ri, l, r, n2; queue<int> q[b * 2]; int find(){ int ix = 1; while(ix < b){ ix <<= 1; if(!seg[ix]) ix++; } return ix - b; } void upd(int ix){ ix += b; while(ix) { seg[ix]--; ix /= 2; } } int sum(int l, int r){ l += b; r += b; int ret = 0; while(l <= r){ if(l & 1) ret += seg[l++]; if(!(r & 1)) ret += seg[r--]; l /= 2; r /= 2; } return ret; } ll count_swaps(vector<int> v){ ll ans = 0; n = v.size(); n2 = n / 2; for(int i = 0; i < n; i++) { if(v[i] < 0) v[i] = -v[i]; else v[i] = v[i] + n2; q[v[i]].emplace(i); seg[b + i] = 1; } for(int i = b - 1; i; i--) seg[i] = seg[i * 2] + seg[i * 2 + 1]; for(int i = 0; i < n2; i++){ li = find(); upd(li); l = v[li]; q[l].pop(); r = l > n2 ? l - n2 : l + n2; ri = q[r].front(); upd(ri); q[r].pop(); ans += sum(0, ri) + (l > n2); } return ans; } /* int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> v(n); for(int& x : v) cin >> x; cout << count_swaps(v); return 0; } */ /* test1 4 2 1 -1 -2 test2 6 -2 2 -2 2 -2 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...