# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
476782 | ponytail | Arranging Shoes (IOI19_shoes) | C++17 | 1096 ms | 2500 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef long long ll;
int n;
int inv(int x){
if(x<0) return -x;
else if(x>n) return x - n;
else return x + n;
}
mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
ll same_size(vector<int> S) {
ll ans1 = 0, ans2 = 0;
n = S.size() / 2;
map<int, queue<int> > mp;
int nxt = 0;
for(int i=0; i<2*n; i++) {
if(mp[inv(S[i])].size()){
ans1 += abs(mp[inv(S[i])].front() - nxt) + abs(i - nxt - 1);
ans2 += (S[i]<0);
nxt += 2;
mp[inv(S[i])].pop();
}
else{
mp[inv(inv(S[i]))].push(i);
}
}
return ans1 / 2 + ans2;
}
ll count_swaps(vector<int> S) {
int nxt = 0;
ll ans = 0;
for(int i=0; i<S.size(); i++) {
if(S[i] < 0) {
for(int j=i-1; j>=nxt; j--) {
swap(S[j], S[j+1]); ans++;
}
for(int j=nxt+1; j<S.size(); j++) {
if(S[j] == -S[nxt]) {
for(int k=j-1; k>=nxt+1; k--) {
swap(S[k], S[k+1]); ans++;
}
break;
}
}
nxt += 2;
}
}
return ans;
}
void solve() {
int n = uniform_int_distribution<int>(1, 5)(rng);// cin >> n;
vector<int> v(2*n);
for(int i=0; i<n; i++) v[i] = -uniform_int_distribution<int>(1, n)(rng);
for(int i=n; i<2*n; i++) {
v[i] = -v[i-n];
}
//shuffle(v.begin(), v.end(), rng);
//for(int i=0; i<2*n; i++) cin >> v[i];
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |