#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<int> idx;
int cost(vector<int> &p) {
// check if the arrangement is valid
for (int i = 0; i < n-1; i++) {
if (p[i] >= p[i+1]+2) return INF;
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (idx[p[j]] < idx[p[i]]) res++;
}
}
return res;
}
int main() {
// n <= 20
cin >> n;
idx.resize(n+1);
vector<int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
idx[h[i]] = i;
}
int ans = INT_MAX;
for (int mask = 0; mask < (1<<n); mask++) {
vector<int> flip;
for (int i = 0; i < n; i++) {
if (mask & (1<<i)) flip.push_back(i);
}
if (flip.size() == 0 || (flip.size() > 0 && flip[0] == 0)) continue;
vector<int> p(n);
iota(p.begin(), p.end(), 1);
int prev = 0;
for (int i = 0; i < flip.size(); i++) {
reverse(p.begin()+prev, p.begin()+flip[i]);
prev = flip[i];
}
reverse(p.begin()+prev, p.end());
ans = min(ans, cost(p));
prev = 0;
for (int i = 0; i < flip.size(); i++) {
reverse(p.begin()+prev, p.begin()+flip[i]);
prev = flip[i];
}
reverse(p.begin()+prev, p.end());
}
cout << ans << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < flip.size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < flip.size(); i++) {
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
352 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
352 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
91 ms |
428 KB |
Output is correct |
12 |
Correct |
169 ms |
340 KB |
Output is correct |
13 |
Correct |
179 ms |
340 KB |
Output is correct |
14 |
Correct |
355 ms |
428 KB |
Output is correct |
15 |
Correct |
368 ms |
340 KB |
Output is correct |
16 |
Correct |
354 ms |
340 KB |
Output is correct |
17 |
Incorrect |
342 ms |
424 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
352 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
91 ms |
428 KB |
Output is correct |
12 |
Correct |
169 ms |
340 KB |
Output is correct |
13 |
Correct |
179 ms |
340 KB |
Output is correct |
14 |
Correct |
355 ms |
428 KB |
Output is correct |
15 |
Correct |
368 ms |
340 KB |
Output is correct |
16 |
Correct |
354 ms |
340 KB |
Output is correct |
17 |
Incorrect |
342 ms |
424 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
352 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
91 ms |
428 KB |
Output is correct |
12 |
Correct |
169 ms |
340 KB |
Output is correct |
13 |
Correct |
179 ms |
340 KB |
Output is correct |
14 |
Correct |
355 ms |
428 KB |
Output is correct |
15 |
Correct |
368 ms |
340 KB |
Output is correct |
16 |
Correct |
354 ms |
340 KB |
Output is correct |
17 |
Incorrect |
342 ms |
424 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
352 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
91 ms |
428 KB |
Output is correct |
12 |
Correct |
169 ms |
340 KB |
Output is correct |
13 |
Correct |
179 ms |
340 KB |
Output is correct |
14 |
Correct |
355 ms |
428 KB |
Output is correct |
15 |
Correct |
368 ms |
340 KB |
Output is correct |
16 |
Correct |
354 ms |
340 KB |
Output is correct |
17 |
Incorrect |
342 ms |
424 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |