#include "shoes.h"
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
#define all(x) x.begin(),x.end()
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = (int)s.size();
if(n <= 16){
vector<int> neg;
for(int i = 0; i < n; i++){
if(s[i] < 0){
neg.push_back(i);
}
}
const int MAX = 16;
bitset<MAX> mark;
int ans = INT32_MAX;
do{
mark.reset();
vector<int> ar(n);
int aux = 0;
for(int i = 0; i < n/2; i++){
ar[aux] = neg[i];
for(int j = 0; j < n; j++){
if(mark[j] == false and s[j] == -s[ar[aux]]){
ar[aux+1] = j;
mark[j] = true;
break;
}
}
aux += 2;
}
vector<int> pos(n), num(n);
for(int i = 0; i < n; i++) pos[i] = num[i] = i;
/*for(int i = 0; i < n; i++){
cout << ar[i] << " ";
}*/
//cout << "\n";
int swp = 0;
for(int i = 0; i < n; i++){
swp += abs(i-pos[ar[i]]);
//cout << "sumo: " << abs(i-pos[ar[i]]) << "\n";
if(pos[ar[i]] < i){
for(int j = pos[ar[i]]+1; j <= i; j++){
pos[ num[j] ]--;
}
pos[ ar[i] ] = i;
}
if(i < pos[ar[i]]){
for(int j = pos[ar[i]]-1; j >= i; j--){
pos[num[j]]++;
}
pos[ ar[i] ] = i;
}
for(int i = 0; i < n; i++) num[pos[i]] = i;
/*cout << "asi queda el nuevo arr: " << "\n";
for(int i = 0; i < n; i++) cout << num[i] << " ";
cout << "\n";*/
}
//cout << "\n" << swp << "\n";
ans = min(ans,swp);
}while(next_permutation(all(neg)));
return ans;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
2 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
300 KB |
Output is correct |
25 |
Correct |
6 ms |
212 KB |
Output is correct |
26 |
Correct |
57 ms |
280 KB |
Output is correct |
27 |
Correct |
51 ms |
280 KB |
Output is correct |
28 |
Correct |
60 ms |
276 KB |
Output is correct |
29 |
Correct |
49 ms |
284 KB |
Output is correct |
30 |
Correct |
49 ms |
280 KB |
Output is correct |
31 |
Correct |
47 ms |
284 KB |
Output is correct |
32 |
Correct |
50 ms |
212 KB |
Output is correct |
33 |
Correct |
54 ms |
276 KB |
Output is correct |
34 |
Correct |
61 ms |
284 KB |
Output is correct |
35 |
Correct |
50 ms |
280 KB |
Output is correct |
36 |
Correct |
49 ms |
284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
304 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
52 ms |
280 KB |
Output is correct |
14 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
260 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
232 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
26 ms |
2104 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
2 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
300 KB |
Output is correct |
25 |
Correct |
6 ms |
212 KB |
Output is correct |
26 |
Correct |
57 ms |
280 KB |
Output is correct |
27 |
Correct |
51 ms |
280 KB |
Output is correct |
28 |
Correct |
60 ms |
276 KB |
Output is correct |
29 |
Correct |
49 ms |
284 KB |
Output is correct |
30 |
Correct |
49 ms |
280 KB |
Output is correct |
31 |
Correct |
47 ms |
284 KB |
Output is correct |
32 |
Correct |
50 ms |
212 KB |
Output is correct |
33 |
Correct |
54 ms |
276 KB |
Output is correct |
34 |
Correct |
61 ms |
284 KB |
Output is correct |
35 |
Correct |
50 ms |
280 KB |
Output is correct |
36 |
Correct |
49 ms |
284 KB |
Output is correct |
37 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
2 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
300 KB |
Output is correct |
25 |
Correct |
6 ms |
212 KB |
Output is correct |
26 |
Correct |
57 ms |
280 KB |
Output is correct |
27 |
Correct |
51 ms |
280 KB |
Output is correct |
28 |
Correct |
60 ms |
276 KB |
Output is correct |
29 |
Correct |
49 ms |
284 KB |
Output is correct |
30 |
Correct |
49 ms |
280 KB |
Output is correct |
31 |
Correct |
47 ms |
284 KB |
Output is correct |
32 |
Correct |
50 ms |
212 KB |
Output is correct |
33 |
Correct |
54 ms |
276 KB |
Output is correct |
34 |
Correct |
61 ms |
284 KB |
Output is correct |
35 |
Correct |
50 ms |
280 KB |
Output is correct |
36 |
Correct |
49 ms |
284 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
2 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
212 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
1 ms |
212 KB |
Output is correct |
45 |
Correct |
1 ms |
304 KB |
Output is correct |
46 |
Correct |
1 ms |
212 KB |
Output is correct |
47 |
Correct |
52 ms |
280 KB |
Output is correct |
48 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
49 |
Halted |
0 ms |
0 KB |
- |