oj.uz

Submission #13229

# Submission time Handle Problem Language Result Execution time Memory
13229 2015-02-04T19:27:30 Z baneling100 Collider (IZhO11_collider) C++
100 / 100
 56 ms 4048 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4048 KB Output is correct
2 Correct 5 ms 4048 KB Output is correct
3 Correct 8 ms 4048 KB Output is correct
4 Correct 21 ms 4048 KB Output is correct
5 Correct 45 ms 4048 KB Output is correct
6 Correct 47 ms 4048 KB Output is correct
7 Correct 49 ms 4048 KB Output is correct
8 Correct 26 ms 4048 KB Output is correct
9 Correct 56 ms 4048 KB Output is correct
10 Correct 39 ms 4048 KB Output is correct