Submission #242005

#	Time	Username	Problem	Language	Result	Execution time	Memory
242005		alexandra_udristoiu	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	590 ms	90616 KiB

scrivener

int nr;
int d[20][1000003], pos[1000003], num[1000003];
char s[1000003];

void Init() {}

void TypeLetter(char c) {
    nr++;
    s[nr] = c;
    pos[nr] = nr;
    num[nr] = 1 + num[nr - 1];
    d[0][nr] = pos[nr - 1];
    for(int ii = 1; ii < 20; ii++){
        d[ii][nr] = d[ii - 1][ d[ii - 1][nr] ];
    }
}

void UndoCommands(int x){
    nr++;
    pos[nr] = pos[nr - x - 1];
    num[nr] = num[nr - x - 1];
    for(int ii = 0; ii < 20; ii++){
        d[ii][nr] = d[ii][ pos[nr] ];
    }
}

char GetLetter(int p) {
    int ii, x = pos[nr];
    p = num[nr] - p - 1;
    for(ii = 19; ii >= 0; ii--){
        if(p >= (1 << ii) ){
            x = d[ii][x];
            p -= (1 << ii);
        }
    }
    return s[x];
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40