Submission #13266

#	Time	Username	Problem	Language	Result	Execution time	Memory
13266		dohyun0324	Collider (IZhO11_collider)	C++98	90 / 100	214 ms	11924 KiB

collider

#include<stdio.h>
#include<math.h>
#include<string.h>
int x,y,w,n,k,m,top[3010];
char arr[1000010],dap,t,a[1000010],c,bucket[3010][3010];
void update(int x,int y)
{
    int i,j,cnt=0,r;
    for(i=1;i<=w;i++){
        if(top[i]+cnt>=x){
            for(j=1;j<=k*2;j++){
                if(bucket[i][j]!=0) cnt++;
                if(cnt==x){t=bucket[i][j]; bucket[i][j]=0, top[i]--;break;}
            }
            break;
        }
        cnt+=top[i];
    }
    cnt=0;
    for(i=1;i<=w;i++){
        if(top[i]+cnt>=y){
            for(j=1;j<=k*2;j++){
                if(bucket[i][j]!=0) cnt++;
                if(cnt==y) break;
            }
            for(r=k*2;r>=j+1;r--) bucket[i][r]=bucket[i][r-1];
            bucket[i][j]=t; top[i]++;
            break;
        }
        cnt+=top[i];
    }
}
char query(int x)
{
    int i,j,cnt=0;
    for(i=1;i<=w;i++){
        if(top[i]+cnt>=x){
            for(j=1;j<=k*2;j++){
                if(bucket[i][j]!=0) cnt++;
                if(cnt==x) return bucket[i][j];
            }
            break;
        }
        cnt+=top[i];
    }
}
void clearing()
{
    int i,j,cnt=0;
    for(i=1;i<=w;i++){
        for(j=1;j<=k*2;j++){
            if(bucket[i][j]!=0) arr[++cnt]=bucket[i][j];
        }
    }
    w=0;
    memset(top,0,sizeof top);
    memset(bucket,0,sizeof bucket);
    for(i=1;i<=n;i++){
        if(i%k==1) w++;
        bucket[w][++top[w]]=arr[i];
    }
}
int main()
{
    int i;
    scanf("%d %d",&n,&m);
    scanf("%s",a);
    for(i=n;i>=1;i--) a[i]=a[i-1]; a[0]=0;
    k=sqrt(n);
    for(i=1;i<=n;i++)
    {
        if(i%k==1) w++;
        bucket[w][++top[w]]=a[i];
    }
    for(i=1;i<=m;i++)
    {
        scanf(" %c",&c);
        if(c=='a'){
            scanf("%d %d",&x,&y);
            update(x,y);
        }
        else{
            scanf("%d",&x);
            dap=query(x);
            printf("%c\n",dap);
        }
        if(i%k==0) clearing();
    }
    return 0;
}

• Subtask 1: 90 / 100