比赛 |
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;
}