JOI2014春day1-growing

解けてなくても記事を書こう(適当)
45点
／＼となればよい
おおきいやつをどうするかとかクッソわかりにくいので(例えば2,3,4,5,6,1,7,10,9とかだと10を動かした後～とか考えると死ぬことがわかる)小さいやつを端っこに投げていきましょう
近い方に投げてよいです(端っこに投げる場合どうなげても他の順番は変わらないので(端っこでないとそうはいかないのでやばい)また、先に操作しようが後に操作しようが変わらない(端っこなら!!))
同じ長さがある(うざい)
半分より左なら左に,右なら右に投げる?
222111111111 で1を左に投げることになりやばい
左右との差が小さい順に見ていく 左に投げたら左を+1,右に投げたら右を-1(ナイーブにswap)
ここらへんの実装が面倒
満点解法にするにはswapではなく、「イテレータの指す値を削除」,「左から何番目の値か」にO(logn)以下で応えてくれる構造がほしいけどわからん

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define ALL(c) (c).begin(),(c).end()
int n;
vector<int> vc,syu,kosu;
int main(){
	scanf("%d",&n);
	rep(i,n){
		int d;
		scanf("%d",&d);
		vc.push_back(d);
	}
	syu=vc;
	sort(ALL(syu));
	int cnt=1;
	rep1(i,n-1){
		if(syu[i]==syu[i-1]) cnt++;
		else{
			kosu.push_back(cnt);
			cnt=1;
		}
	}
	kosu.push_back(cnt);
	syu.erase(unique(ALL(syu)),syu.end());
//	rep(i,syu.size()) cout << syu[i] << " " << kosu[i] << endl;
	int l=0,r=n-1,ans=0;
	rep(i,syu.size()){
		cnt=0;
		rep(j,n){//?
			bool flag=false;
			if(vc[l+j]==syu[i]){
				cnt++;
				for(int k=l+j;k>l;k--){
					swap(vc[k],vc[k-1]);
					ans++;
				}
				l++;
				flag=true;
			}
			if(cnt==kosu[i]) break;
			if(vc[r-j]==syu[i]){
				cnt++;
				for(int k=r-j;k<r;k++){
					swap(vc[k],vc[k+1]);
					ans++;
				}
				r--;
				flag=true;
			}
			if(flag) j--;
			if(cnt==kosu[i]) break;
		}
//		rep(i,n) cout << vc[i] << " ";
//		cout <<endl<< ans << endl << endl;
	}
	printf("%d\n",ans);
	return 0;
}