제출 #781833

#제출 시각아이디문제언어결과실행 시간메모리
781833acatmeowmeowArranging Shoes (IOI19_shoes)C++14
10 / 100
1083 ms17260 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define int long long void remove(set<int>&lef, vector<set<int>>&pos, vector<signed>&s, int p) { if (s[p] < 0) lef.erase(p); else pos[s[p]].erase(p); if (s[p + 1] < 0) lef.erase(p + 1); else pos[s[p + 1]].erase(p + 1); } void add(set<int>&lef, vector<set<int>>&pos, vector<signed>&s, int p) { if (s[p] < 0) lef.insert(p); else pos[s[p]].insert(p); if (s[p + 1] < 0) lef.insert(p + 1); else pos[s[p + 1]].insert(p + 1); } long long count_swaps(std::vector<signed> s) { ios::sync_with_stdio(false); cin.tie(nullptr); set<int> lef, rig; int n = s.size()/2; vector<set<int>> pos(n + 5); for (int i = 0; i < 2*n; i++) { if (s[i] > 0) pos[s[i]].insert(i); if (s[i] < 0) lef.insert(i); } int ans = 0, index = 0; while (index < 2*n) { int l = *lef.begin(); for (int i = l - 1; i >= index; i--) { remove(lef, pos, s, i); swap(s[i], s[i + 1]); add(lef, pos, s, i); ans++; } lef.erase(index); int r = *pos[-s[index]].begin(); index++; for (int i = r - 1; i >= index; i--) { remove(lef, pos, s, i); swap(s[i], s[i + 1]); add(lef, pos, s, i); ans++; } pos[s[index]].erase(index); index++; } return ans; } /*signed main() { int n; cin >> n; vector<signed> arr(2*n); for (int i = 0; i < 2*n; i++) cin >> arr[i]; cout << count_swaps(arr) << '\n'; return 0; }*/
#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...