#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 ;i ++){
per.push_back(i) ;
}
for(auto u : v){
//cout<< u.first <<" " << u.second <<"..\n" ;
}
do{
bool bad = 0 ;
ll ret1 = 0 ;
for(int i = 1 ;i < n;i+=2){
int x = s[per[i-1]] , y = s[per[i]] ;
if(!(x == -y && x < y)){
bad = 1;
break ;
}
ret1+= abs(i - per[i]) ;
ret1+= abs((i-1) - per[i-1]) ;
}
if(!bad){
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){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
376 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
416 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Execution timed out |
1092 ms |
256 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Execution timed out |
1088 ms |
23276 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |