TopCoder SRM 755 Div2 Hard OneHandSort2

なんか今回Div2 HardもDiv1 Hardも既視感漂うんだよな…。
https://community.topcoder.com/stat?c=problem_statement&pm=15417

問題

基本的な設定はDiv1 Easyと同じである。
TopCoder SRM 755 Div1 Easy Div2 Medium OneHandSort - kmjp's blog

ただしこちらは数列長が長いうえ、最小移動回数を求める問題となっている。

解法

与えられた数列をP[i]とし、これを昇順に並べ替えるとする。
N頂点のグラフを考え、各値を行くべき場所に向けて、P[i]→iと有向辺を張ることを考える。
そうするといくつかの閉路ができる。
長さ2以上の閉路がある場合、(長さ+1)手あれば閉路内の要素を行くべき場所に移動できるので、各閉路長を数えればよい。

int vis[505050];

class OneHandSort2 {
	public:
	int minMoves(int N, vector <int> P, int a, int b) {
		set<int> S;
		int i;
		FOR(i,N) S.insert(i);
		FORR(p,P) S.erase(p);
		for(i=P.size();i<N;i++) {
			ll tmp=(1LL*P.back()*a+b)%N;
			auto it=S.lower_bound(tmp);
			if(it==S.end()) it=S.begin();
			P.push_back(*it);
			S.erase(it);
		}
		ZERO(vis);
		int ret=0;
		FOR(i,N) {
			if(vis[i]) continue;
			if(P[i]==i) continue;
			int cur=i;
			int len=0;
			while(P[cur]!=i) {
				len++;
				cur=P[cur];
				vis[cur]=1;
			}
			vis[i]=1;
			ret+=len+2;
		}
		return ret;
		
	}
}

まとめ

入力形式が無駄にややこしい…。