Submission #18521

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18521	2016-02-07T08:23:56 Z	suhgyuho_william	Collider (IZhO11_collider)	C++	100 / 100	124 ms	13900 KB

collider

#include <stdio.h>

int N,M,last;
int bucket[1010][2010],cnt[1010];
char s[1000010];

#define MOD 1000

int b,t;
void where(int x){
	int i,sum = 0;

	for(i=0; i<=last; i++){
		if(sum < x && x <= sum+cnt[i]){
			b = i;
			break;
		}
		sum += cnt[i];
	}
	t = x-sum-1;
}

void pop(int x,int y){
	int i;

	for(i=y; i<cnt[x]-1; i++){
		bucket[x][i] = bucket[x][i+1];
	}
	cnt[x]--;
}

void push1(int x,int y,int v){
	int i;

	for(i=cnt[x]-1; i>=y; i--){
		bucket[x][i+1] = bucket[x][i];
	}
	bucket[x][y] = v;
	cnt[x]++;
}
void push2(int x,int y,int v){
	int i;

	for(i=cnt[x]-1; i>y; i--){
		bucket[x][i+1] = bucket[x][i];
	}
	bucket[x][y+1] = v;
	cnt[x]++;
}

int tmp[1000010];
void setting(){
	int i,j,rear;

	rear = -1;
	for(i=0; i<=last; i++){
		for(j=0; j<cnt[i]; j++){
			rear++;
			tmp[rear] = bucket[i][j];
		}
		cnt[i] = 0;
	}
	for(i=0; i<N; i++){
		bucket[i/MOD][i%MOD] = tmp[i];
		cnt[i/MOD]++;
	}
}

int main(){
	int i,j;
	int x,y;
	int v;
	char op[5];
	//freopen("input.txt","r",stdin);

	scanf("%d %d",&N,&M);
	scanf("%s",s);
	for(i=0; i<N; i++){
		bucket[i/MOD][i%MOD] = s[i]-'x'+1;
		cnt[i/MOD]++;
	}
	last = ((N-1)/MOD);
	for(i=1; i<=M; i++){
		/*for(x=1; x<=N; x++){
			where(x);
			printf("%c",'w'+bucket[b][t]);
		}
		printf("\n");*/
		scanf("%s",op);
		if(op[0] == 'a'){
			scanf("%d %d",&x,&y);
			if(x == y) continue;
			where(x);
			v = bucket[b][t];
			pop(b,t);
			if(x < y){
				where(y-1);
				push2(b,t,v);
			}else{
				where(y);
				push1(b,t,v);
			}
		}else if(op[0] == 'q'){
			scanf("%d",&x);
			where(x);
			printf("%c\n",'w'+bucket[b][t]);
		}else{
			while(true){}
		}
		if(i%MOD == 0) setting();
	}

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	13900 KB	Output is correct
2	Correct	11 ms	13900 KB	Output is correct
3	Correct	6 ms	13900 KB	Output is correct
4	Correct	39 ms	13900 KB	Output is correct
5	Correct	73 ms	13900 KB	Output is correct
6	Correct	91 ms	13900 KB	Output is correct
7	Correct	100 ms	13900 KB	Output is correct
8	Correct	50 ms	13900 KB	Output is correct
9	Correct	124 ms	13900 KB	Output is correct
10	Correct	78 ms	13900 KB	Output is correct