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 "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 110;
bool used[N];
int fenwick[N];
void update(int ind, int diff, int n) {
while (ind <= n) {
fenwick[ind] += diff;
ind += (ind & (-ind));
}
}
int sm(int ind) {
int ans = 0;
while (ind > 0) {
ans += fenwick[ind];
ind -= (ind & (-ind));
}
return ans;
}
ll count_swaps(vector<int> S) {
int n = (int)S.size() / 2;
if (n <= 1000) {
ll ans = 0;
for (int i = 0; i < n; i++) {
int ind1 = -1, ind2 = -1;
for (int j = 2 * i; j < 2 * n; j++) {
if (S[j] < 0) {
ind1 = j;
break;
}
}
int x = S[ind1];
for (int j = ind1; j > 2 * i; j--) {
ans++;
swap(S[j], S[j - 1]);
}
for (int j = 2 * i + 1; j < 2 * n; j++) {
if (S[j] == -x) {
ind2 = j;
break;
}
}
for (int j = ind2; j > 2 * i + 1; j--) {
ans++;
swap(S[j], S[j - 1]);
}
}
return ans;
}
bool ch = true;
for (auto& it : S) {
if (abs(it) != abs(S[0])) ch = false;
}
if (ch) {
//cout << "?\n";
vector <int> a;
vector <int> b;
for (int i = 0; i < 2 * n; i++) {
if (S[i] < 0) a.push_back(i + 1);
else b.push_back(i + 1);
update(i + 1, 1, 2 * n);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += sm(a[i] - 1); update(a[i], -1, 2 * n);
ans += sm(b[i] - 1); update(b[i], -1, 2 * n);
}
return ans;
}
}
/*
int main() {
cout << count_swaps({ -2, 2, 2, -2, -2, 2 }) << "\n";
}
*/
Compilation message (stderr)
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
78 | }
| ^
# | 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... |