CodeChef-CARDSHUF : Card Shuffle

問題概要

N(<10^5)枚の1~Nが書かれたカードがある。これを上から何枚かとって上からそのまま置いたり逆順に置いたりする。M(<10^5)回操作した後カードがどのような順番になっているかをシミュレートする問題。

解法

区間で扱う。もちろん区間はどんどん細分化されていくので、適当な回数毎に置換を行い区間をまっさらに整備する。整備のタイミングはsqrt(N)くらいにしておけばよさげ。かなり好きな問題。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int TERM = 300;
const int MAX_N = 1e5;
const int MAX_M = 1e5;

struct range{
	int from, to;
	bool forward;
};


int sz;
range stack[MAX_M];

int N, M;
int perm[MAX_N], tmp_perm[MAX_N];

void init(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++){
		perm[i] = i;
	}
	sz = 1;
	stack[0] = (range){0, N, true};
}

void initialize(){
	int p = 0;
	for(int i=sz-1; i>=0; i--){
		range r = stack[i];
		if(r.forward){
			for(int j=r.from; j<r.to; j++){
				tmp_perm[p++] = perm[j];
			}
		}
		else{
			for(int j=r.to-1; j>=r.from; j--){
				tmp_perm[p++] = perm[j];
			}
		}
	}

	for(int i=0; i<N; i++){
		perm[i] = tmp_perm[i];
	}

	sz = 1;
	stack[0] = (range){0, N, true};
}

void shrink(int n, vector<range>& Xs){
	for(int sum = 0; ; sz--){
		range r = stack[sz-1];
		int len = r.to - r.from;
		if(sum + len >= n){
			if(sum + len == n){
				Xs.push_back(r);
				sz--;
			}
			else if(r.forward){
				Xs.push_back((range){r.from, r.to - (sum + len - n), true});
				stack[sz-1] = (range){r.to - (sum + len - n), r.to, true};
			}
			else{
				Xs.push_back((range){r.from + (sum+len-n), r.to, false});
				stack[sz-1] = (range){r.from, r.from + (sum+len-n), false};
			}
			break;
		}
		else{
			Xs.push_back(r);
			sum += len;
		}
	}
}

void put_forward(const vector<range>& Xs){
	for(int i=(int)Xs.size()-1; i>=0; i--){
		stack[sz++] = Xs[i];
	}
}

void put_backward(const vector<range>& Xs){
	for(int i=0, M=(int)Xs.size(); i<M; i++){
		range r = Xs[i];
		r.forward = !r.forward;
		stack[sz++] = r;
	}
}

void proc(){
	int A, B, C;
	scanf("%d%d%d", &A, &B, &C);
	vector<range> As, Bs, Cs;

	shrink(A, As);
	shrink(B, Bs);
	put_forward(As);
	shrink(C, Cs);
	put_backward(Bs);
	put_forward(Cs);

}

void prn(){
	int p = 0;
	for(int i=sz-1; i>=0; i--){
		range r = stack[i];
		if(r.forward){
			for(int j=r.from; j<r.to; j++){
				printf("%d%c", perm[j]+1, (++p==N ? '\n': ' '));
			}
		}
		else{
			for(int j=r.to-1; j>=r.from; j--){
				printf("%d%c", perm[j]+1, (++p==N ? '\n': ' '));
			}
		}
	}
}

void solve(){
	for(int i=0; i<M; i++){
		if(i%TERM == 0){
			initialize();
		}
		proc();
	}

	prn();
}

int main(){
	init();
	solve();

	return 0;
}