#include<bits/stdc++.h>
#include "shoes.h"
#define I inline void
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 3000 + 7 , mod = 1e9 + 7 ;
// How interesting!
int n;
long long count_swaps(std::vector<int> s) {
map<int,vector<int> > mp ;
ll ret = 1e9 ;
vector<pair<int,int>> v ;
int pos = 0 ;
for(auto u : s){
if(mp[-u].size()){
v.push_back({mp[-u].back() , pos}) ;
mp[-u].pop_back() ;
}
else{
mp[u].push_back(pos) ;
}
pos ++ ;
}
int n = (int) s.size() ;
vector<int> per ;
for(int i = 0 ;i < n / 2 ;i ++){
per.push_back(i) ;
}
for(auto u : v){
//cout<< u.first <<" " << u.second <<"..\n" ;
}
do{
int k = 0;
ll ret1 = 0 ;
for(int i = 0 ; i < n/2 ;i++){
pair<int,int> u = v[per[i]] ;
int l = u.first , r = u.second ;
if(s[l] > s[r])
swap(l , r) ;
ret1+= abs(k - l) ;
ret1+= abs((k+1) - r) ;
k+= 2;
}
ret = min(ret , ret1/2) ;
}
while(next_permutation(per.begin() , per.end())) ;
return ret;
}
Compilation message
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45:11: warning: variable 'u' set but not used [-Wunused-but-set-variable]
45 | for(auto u : v){
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |