-
Notifications
You must be signed in to change notification settings - Fork 1
/
LilysHomework.cpp
executable file
·79 lines (58 loc) · 1.57 KB
/
LilysHomework.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define VI vector< int >
#define MP make_pair
#define PII pair< int , int >
void makePositionsInh( VI& h,vector< PII >& in, int n ){
for( int i = 0 ; i < n ; ++i ){
h[ in[ i ].second ] = i;
}
}
int checkHowMuchSwaps(VI& h,vector<bool>& h2,int n){
int cnt = 0;
int it = 0;
while( it < n ){
int inCnt = 0;
int inIt = it;
if( h2[ it ] == false ){
while( h[ inIt ] != it ){
h2[ inIt ] = true;
inIt = h[ inIt ];
inCnt++;
}
h2[ inIt ] = true;
}
cnt += ( inCnt ) ;
it++;
}
return cnt;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n ;
int x ;
int it = 0;
int cnt = 0;
auto cmp = [](PII a , PII b){ return a.first < b.first; };
cin >> n;
vector < PII > in(n);
vector < int > h(n);
vector < bool > h2( n, false );
for( int i = 0 ; i < n ;++i ){
cin >> x;
in[ i ] = MP( x, i );
}
sort( in.begin(), in.end(), cmp );
makePositionsInh( h, in, n );
int counter1 = checkHowMuchSwaps(h, h2, n);
h2 = vector< bool >( n, false );
reverse( in.begin(), in.end() );
makePositionsInh( h, in, n );
int counter2 = checkHowMuchSwaps(h, h2, n);
cout << min( counter1, counter2 ) << endl;
return 0;
}