# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
491759 | 2021-12-04T09:13:10 Z | White | Money (IZhO17_money) | C++14 | 0 ms | 0 KB |
#pragma optimize ("Ofast") #include<bits\stdc++.h> #define endl "\n" using namespace std; int a[1000001],b[1000001]; bool bqh[1000001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,br=0,now; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; bool yes; for(int i=1;i<n;i++){ if(a[i]!=i){ yes=false; now=i; for(int j=i+1;j<=n;j++){ if(a[j]==i)yes=true; if(yes==true){ if(a[j]==i){ b[now]=i; bqh[j]=true; now++; }else{ while(j<=n && a[j]>a[j-1]){ b[now]=a[j]; bqh[j]=true; now++; j++; } yes=false; } } } //cout<<"OOOOOO"<<now<<endl; for(int j=i;j<=n;j++){ if(bqh[j]==false){ b[now]=a[j]; now++; } } br++; //cout<<i<<"dwa"<<br<<endl; //cout<<b[1]<<b[2]<<endl; for(int j=i;j<=n;j++){ a[j]=b[j]; bqh[j]=false; } } } if(br!=0)br++; cout<<br<<endl; return 0; }