| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 476767 | ponytail | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 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) {
ll wow = S.size() / 2;
return wow *(wow-1) / 2;
int nxt = 0;
ll ans = 0;
map<int, vector<int> > mp;
for(int i=0; i<S.size(); i++) {
mp[abs(S[i])].push_back(S[i]);
}
for(auto x: mp) {
ans += same_size(x.second);
}
map<int, int> freq;
for(int i=0; i<S.size(); i++) {
if(freq[abs(S[i])] & 1) S[i] = abs(S[i]);
else S[i] = -abs(S[i]);
freq[abs(S[i])]++;
}
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, 4)(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);
cout <<"Input:\n";
cout << n <<" \n";
for(int x:v) cout << x<<" ";
cout<<"\nOutput:\n";
cout << count_swaps(v) << "\n";
}
int main() {
for(int i=0; i<100; i++) {
solve();
}
}