Submission #714005

#TimeUsernameProblemLanguageResultExecution timeMemory
714005TheConverseEngineerArranging Shoes (IOI19_shoes)C++17
10 / 100
1054 ms71460 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; #define FOR(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define sqr(x) ((ll)(x))*(x) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; int N; stack<int> ofSz[100003]; ll count_swaps(vi S) { N = sz(S)/2; for (int i = 2*N-1; i >= 0; i--) ofSz[abs(S[i])].push(i); ll ans = 0; vector<pii> pairs; FOR(i, 1, N+1) { while (!ofSz[i].empty()) { int a = ofSz[i].top(); ofSz[i].pop(); pairs.emplace_back(a, ofSz[i].top()); ofSz[i].pop();\ if (S[a] > 0) ans++; } } sort(all(pairs)); set<int> moved; for (pii i : pairs) { ans += i.second - i.first - 1 - std::distance(moved.begin(), moved.lower_bound(i.second)) + distance(moved.begin(), moved.lower_bound(i.first)); moved.insert(i.second); } return ans; } /*int main() { cin.tie(0)->sync_with_stdio(0); int _N; vi _s; cin >> _N; _s.resize(_N); FOR(i, 0, _N) cin >> _s[i]; cout << count_swaps(_s); } */
#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...