TCO2012 Round2C Hard FlattenOut

問題

n個の土地が円周上に並んでいる。
それぞれの土地の高さはheight[i]である。

この土地に対して次のような操作をT回行う。
heightが正であるような土地i全てについて、height[i]を1減らし、height[(i + 1) % n]を1増やす。
この操作は全て同時に行われる。

操作を終えた時点でのそれぞれの土地の高さを求めよ。

制約条件

n≦50
T≦10^16
-10^16≦height[i]≦10^16

方針

シミュレートするだけ。

全ての土地の高さが正になってたら、もう更新はない。
全ての土地の高さが0以下でも更新はないので終了する。

全ての土地の高さが0または1だったらT % n右にシフトするだけ。

それ以外の場合、
正, 正, ..., 正, 負という列で、最初の正が最後の負を埋めることになる。
すると、正の土地または負の土地の数が必ず一つ減るので、
この操作は50回程度で終了することがわかるので、愚直にシミュレートすればいい。

ソースコード

class FlattenOut {
	public:
	vector<long long> simulateIt(vector<long long> height, long long T) {
		
		int n = height.size();
		
		while(T){
			bool posi = 0, nega = 0, zeroone = 1;
			rep(i, n){
				if(height[i] > 0) posi = 1;
				else nega = 1;
				if(height[i] != 0 && height[i] != 1) zeroone = 0;
			}
			if(!posi || !nega) return height;
			if(zeroone){
				if(T % n) rotate(height.begin(), height.begin() + n - T % n, height.end());
				return height;
			}
			
			ll mn = T;
			vector<pi> ps;
			rep(i, n) if(height[i] <= 0 && height[(i + 1) % n] > 0){
				int j = 0;
				for(; j < n; j++) if(height[(i + 1 + j) % n] <= 0) break;
				
				ps.pb(mp((i + 1) % n, j));
				mn = min(mn, -height[(i + j + 1) % n] + 1);
				mn = min(mn, height[(i + 1) % n]);
				
			}
			rep(i, ps.size()){
				int a = ps[i].first, b = ps[i].second;
				height[a] -= mn;
				height[(a + b) % n] += mn;
			}
			T -= mn;
		}
		return height;
	}
};