Submission #13229

#	Time	Username	Problem	Language	Result	Execution time	Memory
13229		baneling100	Collider (IZhO11_collider)	C++98	100 / 100	56 ms	4048 KiB

collider

#include <stdio.h>
#include <math.h>
#define N_MAX 1000000
#define B_MAX 1000

int N, M, B, Bsize[B_MAX+1];
char S[N_MAX+2], Bucket[B_MAX+1][(B_MAX<<1)+2];

void divideBucket(void) {

    int i, j, K=N/B;

    for(i=1 ; i<=B-1 ; i++) {
        Bsize[i]=K;
        for(j=1 ; j<=K ; j++)
            Bucket[i][j]=S[(i-1)*K+j];
    }
    Bsize[B]=N-(B-1)*K;
    for(i=1 ; i<=Bsize[B] ; i++)
        Bucket[B][i]=S[(B-1)*K+i];
}

char eraseChar(int loc) {

    int i, j, sum=0;
    char c;

    for(i=1 ; i<=B-1 ; i++) {
        if(loc<=sum+Bsize[i])
            break;
        sum+=Bsize[i];
    }
    Bsize[i]--;
    loc-=sum;
    c=Bucket[i][loc];
    for(j=loc ; j<=Bsize[i] ; j++)
        Bucket[i][j]=Bucket[i][j+1];
    return c;
}

void insertChar(int loc, char c) {

    int i, j, sum=0;

    for(i=1 ; i<=B-1 ; i++) {
        if(loc<=sum+Bsize[i])
            break;
        sum+=Bsize[i];
    }
    Bsize[i]++;
    loc-=sum;
    for(j=Bsize[i] ; j>=loc+1 ; j--)
        Bucket[i][j]=Bucket[i][j-1];
    Bucket[i][loc]=c;
}

char findChar(int loc) {

    int i, sum=0;

    for(i=1 ; i<=B-1 ; i++) {
        if(loc<=sum+Bsize[i])
            break;
        sum+=Bsize[i];
    }
    return Bucket[i][loc-sum];
}

int main(void) {

    int i, j, k, x, y, cnt=0, sum;
    char c;

    scanf("%d %d %s ",&N,&M,S+1);
    B=sqrt(N);
    divideBucket();
    for(i=1 ; i<=M ; i++) {
        scanf("%c ",&c);
        if(c=='a') {
            scanf("%d %d ",&x,&y);
            insertChar(y,eraseChar(x));
            if(!(++cnt%B)) {
                sum=0;
                for(j=1 ; j<=B ; j++) {
                    for(k=1 ; k<=Bsize[j] ; k++)
                        S[sum+k]=Bucket[j][k];
                    sum+=Bsize[j];
                }
                divideBucket();
            }
        }
        else {
            scanf("%d ",&x);
            printf("%c\n",findChar(x));
        }
    }
    return 0;
}

• Subtask 1: 100 / 100