Submission #18449

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18449	2016-02-02T12:21:28 Z	chan492811	Collider (IZhO11_collider)	C++	100 / 100	347 ms	33992 KB

collider

#include <cstdio>
#include <malloc.h>
using namespace std;
int n,m,sqrtn;
struct node{
    char data;
    node *next,*prev;
};
node *front[100000],*finding;
char arr[1000010];
void find(int a){
    int i=0;
    while(i*sqrtn+sqrtn<a) i++; finding=front[i]; i=i*sqrtn;
    while(i<a) finding=finding->next,i++;
}
int main(){
    int i,j,a,s;
    char flag,data;
    node *temp,*prev,*newnode;
    scanf("%d %d %s\n",&n,&m,arr);
    for(i=1;i*i<n;i++); sqrtn=i; j=0; prev=(node *)malloc(sizeof(node));
    for(i=0;i<n;i++){
        temp=(node *)malloc(sizeof(node)); temp->data=arr[i]; temp->prev=prev; prev->next=temp;
        if(j*sqrtn==i){
            front[j++]=temp;
        }
        prev=temp;
    } temp=(node *)malloc(sizeof(node)); temp->data=arr[i]; temp->prev=prev; prev->next=temp;
    for(i=0;i<m;i++){
        scanf("%c ",&flag);
        if(flag=='a'){
            scanf("%d %d\n",&a,&s); j=0; a--; s--; if(a==s) continue;
            find(a); data=finding->data; temp=finding; //finding=a
            temp->next->prev=temp->prev; temp->prev->next=temp->next;
            for(j=0;j*sqrtn<n;j++) if(j*sqrtn>=a) front[j]=front[j]->next; free(temp);
            find(s); temp=finding;
            newnode=(node *)malloc(sizeof(node)); newnode->data=data; newnode->next=temp; newnode->prev=temp->prev;
            temp->prev=newnode; newnode->prev->next=newnode;
            for(j=0;j*sqrtn<n;j++) if(j*sqrtn>=s) front[j]=front[j]->prev;
        }else{
            scanf("%d\n",&a); a--;
            find(a);
            printf("%c\n",finding->data);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2840 KB	Output is correct
2	Correct	5 ms	2840 KB	Output is correct
3	Correct	15 ms	5876 KB	Output is correct
4	Correct	121 ms	27788 KB	Output is correct
5	Correct	188 ms	27788 KB	Output is correct
6	Correct	259 ms	30956 KB	Output is correct
7	Correct	289 ms	33992 KB	Output is correct
8	Correct	149 ms	33992 KB	Output is correct
9	Correct	347 ms	33992 KB	Output is correct
10	Correct	254 ms	33992 KB	Output is correct