제출 #468676

#제출 시각아이디문제언어결과실행 시간메모리
468676ApiramArranging Shoes (IOI19_shoes)C++14
10 / 100
1100 ms70448 KiB
#include "shoes.h" #include<bits/stdc++.h> using namespace std; long long count_swaps(std::vector<int> s) { int n = s.size(); vector<int>arr=s; vector<deque<int>>neg(1e5); for (int i = 0;i<n;++i) { if (arr[i]>0){ neg[arr[i]].push_back(i); } } int64_t ans = 0; for (int i = 0,cur = 0;i<n;i++){ if (arr[i]<0){ int j = i; while(cur!=j){ swap(arr[j-1],arr[j]); if (arr[j]>0){ for (int k = 0;;++k){ if (neg[arr[j]][k]==j-1){ neg[arr[j]][k]++; break; } } } --j; ans++; } ++cur; j = neg[-arr[cur-1]].front(); neg[-arr[cur-1]].pop_front(); while(j!=cur){ swap(arr[j-1],arr[j]); if (arr[j]>0){ for (int k = 0;;++k){ if (neg[arr[j]][k]==j-1){ neg[arr[j]][k]++; break; } } } --j; ans++; } cur++; } } 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...