제출 #283167

#제출 시각아이디문제언어결과실행 시간메모리
283167Ruba_KArranging Shoes (IOI19_shoes)C++14
10 / 100
1096 ms14276 KiB
#include "shoes.h" #include<bits/stdc++.h> using namespace std ; vector<int > pos[200005]; vector<int>st ; int idx ; int binarysearch(int u){ sort(st.begin() , st.end()); while(st.size() && st.back() > idx)st.pop_back(); if(st.empty())return 0 ; if(st.back() < u)return 0 ; int l = 0 , r = st.size() , md ; while(l < r){ md = (l + r) / 2 ; if(st[md] < u)l = md + 1 ; else r = md ; } return st.size() - l ; } long long count_swaps(vector<int> v) { int n = v.size() / 2 ; for(int i = 0 ; i < n * 2 ; i ++){ pos[v[i] + n] .push_back(i) ; } long long ans = 0 ; for(int i = 2 * n - 1 ; i >= 0 ; i --){ if(v[i] == 0)continue ; idx = i ; int p = v[i] * -1 + n ; pos[v[i] + n].pop_back(); auto u = binarysearch(p); int sum = 0 ; v[pos[p].back()] = 0; sum = u ; sum = i - pos[p].back() - sum - 1 ; st.push_back(pos[p].back()); pos[p].pop_back(); sum += (v[i] < 0); ans += sum ; } return ans; }
#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...