Submission #713721

#TimeUsernameProblemLanguageResultExecution timeMemory
713721TheConverseEngineerArranging Shoes (IOI19_shoes)C++17
10 / 100
45 ms67624 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 - distance(moved.begin(), moved.lower_bound(i.second)); moved.insert(i.second); } 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...