#include "gondola.h" #include<bits/stdc++.h> using namespace std; int valid(int n, int G[]){ set<int> vis; for( int i = 0; i < n; i++ ){ if( vis.find( G[i] ) != vis.end() ) return 0; vis.insert( G[i] ); } int start = 0; for( int i = 0; i < n; i++ ){ if( G[i] <= n ){ start = i; break; } } if( !start ) return 1; int pos = start, next = G[start]; for( int i = 1; i < n; i++ ){ if( G[pos] <= n ){ if( G[pos] != next ) return 0; } pos++; if( pos > n ) pos = 1; next++; if( next > n ) next = 1; } return 1; } //---------------------- int replacement(int n, int a[], int ans[]){ int apos=-1, av; int maxf=0; int minf = 0; unordered_map<int, int> m; for(int i=0;i<n;i++){ if(a[i]<=n) apos = i, av=a[i]; else m[a[i]] = i+1; maxf = max(maxf, a[i]); if(a[minf]>a[i]) minf = i; } if(apos==-1){ apos = minf; av = 1; } queue<int> q; int l=0; for(int i=n+1;i<=maxf;i++){ if(m[i]){ int c = l - 1; ans[l] = (n + av - (apos - m[i] + 1) - 1) % n + l - c; l++; //cout<<apos<<" "<<m[i]<<" "<<av<<endl; while(!q.empty()){ ans[l] = q.front(); q.pop(); l++; } } else q.push(i); } return l; } //---------------------- int countReplacement(int n, int a[]){ if(!valid(n, a)){ //cout<<"No\n"; return 0; } sort(a, a+n); int ans=1; for(int i=0;i<n;i++){ if(a[i]<=n) continue; ans += max((a[i+1]-a[i]-3), 0); } return ans; }