Submission #839143

#TimeUsernameProblemLanguageResultExecution timeMemory
839143DarkMatterArranging Shoes (IOI19_shoes)C++14
85 / 100
47 ms7796 KiB
#include<bits/stdc++.h> #include "shoes.h" using namespace std; long long count_swaps(std::vector<int> v) { int n = v.size(); set<int>s; for (auto& it : v) s.insert(abs(it)); if (s.size() == 1) { long long idx = 0, ans = 0; for (int i = 0; i < n; i++) if (v[i] < 0) ans += abs(i - idx), idx += 2; return ans; } if (n / 2 > 1000) { n /= 2; long long ans = 0; for (long long i = 0; i < n; i++) ans += i; return ans; } vector<bool>vis(n, false); long long ans = 0; vector<int>idx(n); iota(idx.begin(), idx.end(), 0); for (int i = 0; i < n; i++) { if (vis[i]) continue; vis[i] = true; for (int j = i + 1; j < n; j++) { if (!vis[j] && v[j] == -v[i]) { vis[j] = true; int dif = idx[j] - idx[i] - 1; if (idx[i] % 2 == 0 && v[i] < 0) ans += dif; else ans += dif + 1; break; } idx[j]++; } } 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...