#include <bits/stdc++.h>
using namespace std;
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t);
#define forr(i, l, r) for(int i=l; i<r; i++)
#define frange(i, l) forr(i, 0, l)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef long long lli;
typedef vector<vi> vvi;
typedef vector<lli> vll;
typedef vector<bool> vb;
void usaco() {
freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
}
int main() {
// usaco();
int n;
scd(n);
vi vec(n);
vi pos(n);
frange(i, n) {
scd(vec[i]);
vec[i]--;
pos[vec[i]] = i;
}
vector<vi> dp(1<<n, vi(n, 1e9));
// forr(i, 1, 1<<n) {
// frange(j, n) {
// if(i & (1<<j)) {
// if(__builtin_popcount(i) == 1) dp[i][j] = pos[j];
// int k = i ^ (1<<j);
// frange(l, n) {
// if(k & (1<<l)) {
// if(vec[j] + 2 > vec[l]) {
// dp[i][j] = min(dp[i][j], dp[k][l] + abs(pos[j] - __builtin_popcount(k)));
// }
// }
// }
// }
// }
// }
sort(all(vec));
int mi = 1e9;
do {
bool done = true;
forr(i, 1, n) {
if(vec[i] + 2 <= vec[i-1]) done = false;
}
if(!done) continue;
int tot = 0;
frange(i, n) tot += max(0, i - pos[vec[i]]);
mi = min(mi, tot);
}
while(next_permutation(all(vec)));
printf("%d\n", mi/2);
}
Compilation message
Main.cpp: In function 'void usaco()':
Main.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
Main.cpp:30:2: note: in expansion of macro 'scd'
30 | scd(n);
| ^~~
Main.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
Main.cpp:35:3: note: in expansion of macro 'scd'
35 | scd(vec[i]);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
