#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct segtree {
int n; vector<int> t;
segtree(int _n) : n(_n) {
t = vector<int>(2 * n, 0);
}
void set(int x) {
t[x + n] = x;
}
void add(int l, int r, int x) {
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) t[l++] += x;
if (r&1) t[--r] += x;
}
}
int get(int p) {
int res = 0;
for (p += n; p > 0; p /= 2) res += t[p];
return res;
}
};
int64_t slow(vector<int> a) {
int n = a.size();
vector<int> p;
for (int i = 0; i < n; ++i) p.push_back(i);
ll ans = 1e9;
do {
int ok = 1;
for (int i = 0; i < n; i += 2) {
ok &= (abs(a[p[i]]) == a[p[i + 1]]);
}
if (ok) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
cnt += p[i] > p[j];
}
}
ans = min(ans,(ll) cnt);
}
} while (next_permutation(p.begin(), p.end()));
return ans;
}
int64_t count_swaps(vector<int> a) {
int n = a.size();
vector<vector<vector<int>>> pos(n + 1, vector<vector<int>>(2));
for (int i = 0; i < n; ++i) {
pos[abs(a[i])][a[i] > 0].push_back(i);
}
vector<pair<int, int>> ps;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < pos[i][0].size(); ++j) {
ps.push_back({pos[i][0][j], pos[i][1][j]});
}
}
sort(ps.begin(), ps.end(), [](pair<int, int> & x, pair<int, int> & y){
// return x.first < y.first;
return min(x.first, x.second) < min(y.first, y.second);
});
segtree st(n);
for (int i = 0; i < n / 2; ++i) {
st.set(ps[i].first);
st.set(ps[i].second);
}
ll ans = 0;
for (int i = 0; i < n / 2; ++i) {
int tl = 2 * i, tr = 2 * i + 1;
int cl = st.get(ps[i].first);
if (tl > cl) {
assert(false);
// cout << "g1\n";
// return -1;
}
ans += cl - tl;
// cout << "! " << cl << ' ' << tl << '\n';
st.add(0, ps[i].first + 1, 1);
// for (int j = 0; j < n; ++j) {
// cout << st.get(j) << " \n"[j + 1 == n];
// }
int cr = st.get(ps[i].second);
if (tr > cr) {
assert(false);
// cout << "g2\n";
// cout << tr << ' ' << cr << '\n';
// return -1;
}
ans += cr - tr;
// cout << "! " << cr << ' ' << tr << '\n';
st.add(0, ps[i].second + 1, 1);
// for (int j = 0; j < n; ++j) {
// cout << st.get(j) << " \n"[j + 1 == n];
// }
// cout << "after " << i + 1 << " times: " << ans << "\n";
}
return ans;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rng0(ll B) {
return (unsigned long long)rng() % B;
}
vector<int> gen(int n) {
vector<int> ret;
for (int i = 0; i < n; ++i) {
ret.push_back(rng0(n) + 1);
ret.push_back(ret.back() * -1);
}
random_shuffle(ret.begin(), ret.end());
return ret;
}
\
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int tt;
// cin >> tt;
// for (int t = 1; t <= tt; ++t) {
// int n;
// // cin >> n;
// vector<int> a = gen(4);
// // for (auto & x: a) cin >> x;
// // cout << "---- Start test case " << t << " ---- \n";
// // for (auto & x: a) cout << x << " ";
// // cout << "is array\n";
// ll ans = count_swaps(a);
// ll ans2 = slow(a);
// if (ans != ans2) {
// cout << "!!!!!!!!!!!!!!!!\n";
// for (auto & x: a) cout << x << " ";
// cout << "is array\n";
// cout << ans << ' ' << ans2 << '\n';
// exit(0);
// }
// // cout << count_swaps(a) << "\n";
// }
// return 0;
// }
Compilation message
shoes.cpp: In function 'int64_t count_swaps(std::vector<int>)':
shoes.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int j = 0; j < pos[i][0].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
436 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
608 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
0 ms |
360 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
5 ms |
2652 KB |
Output is correct |
21 |
Correct |
5 ms |
2652 KB |
Output is correct |
22 |
Correct |
52 ms |
22264 KB |
Output is correct |
23 |
Correct |
52 ms |
22484 KB |
Output is correct |
24 |
Correct |
51 ms |
22452 KB |
Output is correct |
25 |
Correct |
55 ms |
22496 KB |
Output is correct |
26 |
Correct |
51 ms |
22348 KB |
Output is correct |
27 |
Correct |
50 ms |
22488 KB |
Output is correct |
28 |
Correct |
51 ms |
22488 KB |
Output is correct |
29 |
Correct |
52 ms |
22480 KB |
Output is correct |
30 |
Correct |
53 ms |
22232 KB |
Output is correct |
31 |
Correct |
50 ms |
22456 KB |
Output is correct |
32 |
Correct |
50 ms |
22484 KB |
Output is correct |
33 |
Correct |
48 ms |
22496 KB |
Output is correct |
34 |
Correct |
53 ms |
22488 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
50 ms |
22496 KB |
Output is correct |
38 |
Correct |
49 ms |
22496 KB |
Output is correct |
39 |
Correct |
49 ms |
22496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
84 ms |
27848 KB |
Output is correct |
6 |
Correct |
62 ms |
22988 KB |
Output is correct |
7 |
Correct |
91 ms |
27920 KB |
Output is correct |
8 |
Correct |
52 ms |
22676 KB |
Output is correct |
9 |
Correct |
84 ms |
27844 KB |
Output is correct |
10 |
Correct |
77 ms |
24772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
436 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
608 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
0 ms |
360 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
504 KB |
Output is correct |
41 |
Correct |
1 ms |
600 KB |
Output is correct |
42 |
Correct |
1 ms |
604 KB |
Output is correct |
43 |
Correct |
1 ms |
600 KB |
Output is correct |
44 |
Correct |
1 ms |
600 KB |
Output is correct |
45 |
Correct |
1 ms |
604 KB |
Output is correct |
46 |
Correct |
1 ms |
604 KB |
Output is correct |
47 |
Correct |
1 ms |
604 KB |
Output is correct |
48 |
Correct |
1 ms |
604 KB |
Output is correct |
49 |
Correct |
1 ms |
604 KB |
Output is correct |
50 |
Correct |
1 ms |
612 KB |
Output is correct |
51 |
Correct |
1 ms |
604 KB |
Output is correct |
52 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
436 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
608 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
0 ms |
360 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
0 ms |
348 KB |
Output is correct |
44 |
Correct |
0 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
348 KB |
Output is correct |
47 |
Correct |
0 ms |
348 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
0 ms |
348 KB |
Output is correct |
50 |
Correct |
1 ms |
344 KB |
Output is correct |
51 |
Correct |
1 ms |
344 KB |
Output is correct |
52 |
Correct |
1 ms |
600 KB |
Output is correct |
53 |
Correct |
1 ms |
600 KB |
Output is correct |
54 |
Correct |
5 ms |
2652 KB |
Output is correct |
55 |
Correct |
5 ms |
2652 KB |
Output is correct |
56 |
Correct |
52 ms |
22264 KB |
Output is correct |
57 |
Correct |
52 ms |
22484 KB |
Output is correct |
58 |
Correct |
51 ms |
22452 KB |
Output is correct |
59 |
Correct |
55 ms |
22496 KB |
Output is correct |
60 |
Correct |
51 ms |
22348 KB |
Output is correct |
61 |
Correct |
50 ms |
22488 KB |
Output is correct |
62 |
Correct |
51 ms |
22488 KB |
Output is correct |
63 |
Correct |
52 ms |
22480 KB |
Output is correct |
64 |
Correct |
53 ms |
22232 KB |
Output is correct |
65 |
Correct |
50 ms |
22456 KB |
Output is correct |
66 |
Correct |
50 ms |
22484 KB |
Output is correct |
67 |
Correct |
48 ms |
22496 KB |
Output is correct |
68 |
Correct |
53 ms |
22488 KB |
Output is correct |
69 |
Correct |
0 ms |
348 KB |
Output is correct |
70 |
Correct |
1 ms |
348 KB |
Output is correct |
71 |
Correct |
50 ms |
22496 KB |
Output is correct |
72 |
Correct |
49 ms |
22496 KB |
Output is correct |
73 |
Correct |
49 ms |
22496 KB |
Output is correct |
74 |
Correct |
0 ms |
348 KB |
Output is correct |
75 |
Correct |
0 ms |
348 KB |
Output is correct |
76 |
Correct |
0 ms |
348 KB |
Output is correct |
77 |
Correct |
1 ms |
348 KB |
Output is correct |
78 |
Correct |
84 ms |
27848 KB |
Output is correct |
79 |
Correct |
62 ms |
22988 KB |
Output is correct |
80 |
Correct |
91 ms |
27920 KB |
Output is correct |
81 |
Correct |
52 ms |
22676 KB |
Output is correct |
82 |
Correct |
84 ms |
27844 KB |
Output is correct |
83 |
Correct |
77 ms |
24772 KB |
Output is correct |
84 |
Correct |
0 ms |
348 KB |
Output is correct |
85 |
Correct |
0 ms |
348 KB |
Output is correct |
86 |
Correct |
0 ms |
348 KB |
Output is correct |
87 |
Correct |
1 ms |
504 KB |
Output is correct |
88 |
Correct |
1 ms |
600 KB |
Output is correct |
89 |
Correct |
1 ms |
604 KB |
Output is correct |
90 |
Correct |
1 ms |
600 KB |
Output is correct |
91 |
Correct |
1 ms |
600 KB |
Output is correct |
92 |
Correct |
1 ms |
604 KB |
Output is correct |
93 |
Correct |
1 ms |
604 KB |
Output is correct |
94 |
Correct |
1 ms |
604 KB |
Output is correct |
95 |
Correct |
1 ms |
604 KB |
Output is correct |
96 |
Correct |
1 ms |
604 KB |
Output is correct |
97 |
Correct |
1 ms |
612 KB |
Output is correct |
98 |
Correct |
1 ms |
604 KB |
Output is correct |
99 |
Correct |
1 ms |
604 KB |
Output is correct |
100 |
Correct |
1 ms |
604 KB |
Output is correct |
101 |
Correct |
7 ms |
3228 KB |
Output is correct |
102 |
Correct |
8 ms |
2908 KB |
Output is correct |
103 |
Correct |
90 ms |
29112 KB |
Output is correct |
104 |
Correct |
100 ms |
29176 KB |
Output is correct |
105 |
Correct |
76 ms |
26316 KB |
Output is correct |
106 |
Correct |
83 ms |
29064 KB |
Output is correct |
107 |
Correct |
65 ms |
24528 KB |
Output is correct |
108 |
Correct |
69 ms |
24816 KB |
Output is correct |
109 |
Correct |
57 ms |
24044 KB |
Output is correct |
110 |
Correct |
51 ms |
23512 KB |
Output is correct |
111 |
Correct |
82 ms |
28360 KB |
Output is correct |
112 |
Correct |
82 ms |
27596 KB |
Output is correct |
113 |
Correct |
67 ms |
24520 KB |
Output is correct |
114 |
Correct |
82 ms |
29124 KB |
Output is correct |
115 |
Correct |
81 ms |
29124 KB |
Output is correct |