比赛 20140307 评测结果 AAAAAEEEEE
题目名称 Bessie洗牌法 最终得分 50
用户昵称 cstdio 运行时间 0.580 s
代码语言 C++ 内存使用 8.71 MiB
提交时间 2014-03-07 19:19:44
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
const int SIZEN=100001;
int p[SIZEN]={0};
int ap[SIZEN]={0};
int N,M,Q;
deque<int> finallis;
int atp[SIZEN]={0};
int pp[SIZEN]={0};
int npp[SIZEN][18]={0};
void getpp(int n){
	int i;
	for(i=0;i<N;i++) npp[i][0]=ap[i];
	for(i=0;i<N;i++) pp[i]=i;
	int tot=0;
	while(n){
		if(n&1)	for(i=0;i<N;i++) pp[i]=npp[pp[i]][tot];
		tot++;
		for(i=0;i<N;i++) npp[i][tot]=npp[npp[i][tot-1]][tot-1];
		n>>=1;
	}
}
void work(void){
	int i,j,x=0;
	for(i=0;i<M;i++) pp[i]=i;
	for(i=1;i<=N-M;i++) finallis.push_front(x=ap[x]);
	getpp(N-M+1);
	for(i=0;i<M;i++) finallis.push_front(pp[i]);
}
void answer(void){
	int i,pos;
	for(i=1;i<=Q;i++) scanf("%d",&pos),printf("%d\n",finallis[pos-1]);
}
void init(void){
	scanf("%d%d%d",&N,&M,&Q);
	int i;
	for(i=1;i<=M;i++){
		scanf("%d",&p[i]);
		p[i]--;
	}
	for(i=M+1;i<=N;i++) p[i]=i-1;
	for(i=1;i<=N;i++) ap[p[i]]=i;
}
int main(){
	freopen("shufflegold.in","r",stdin);
	freopen("shufflegold.out","w",stdout);
	init();
	work();
	answer();
	return 0;
}