Submission #779580

#TimeUsernameProblemLanguageResultExecution timeMemory
779580Minindu206Arranging Shoes (IOI19_shoes)C++14
85 / 100
1038 ms3104 KiB
#include "shoes.h" #include <bits/stdc++.h> #define ll long long using namespace std; ll count_swaps(vector<int> s) { ll n = s.size() / 2; if (n == 1) return s[0] > 0; int iseq = 1, fst = s[0], isame = 1; for (int i = 0; i < n; i++) { if (s[i] + s[i + n] != 0 || s[i] > 0) iseq = 0; if (s[i] != fst && s[i] != -fst) isame = 0; } if (iseq) return n * (n - 1) / 2; if (isame) { queue<int> ind; ll ans = 0LL; for (int i = 0; i < 2 * n; i++) if (s[i] < 0) ind.push(i); for (int i = 0; i < 2 * n; i += 2) { int cur = ind.front(); ind.pop(); ans += (abs(cur - i)); } return ans; } int cur = 0; ll ans = 0LL; while (cur < 2 * n) { int val = s[cur]; if (val < 0) { int i = cur + 1; while (s[i] != -val) i++; s.erase(s.begin() + i); s.insert(s.begin() + cur + 1, -val); ans += (i - cur - 1); } else { int i = cur + 1; while (s[i] != -val) i++; s.erase(s.begin() + i); s.insert(s.begin() + cur, -val); ans += (i - cur); } cur += 2; } 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...